Submission #934660
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
struct MaxSegTree{
long n; vector<ll> dat;
//初期化
MaxSegTree(long _n){
n=1;
while(n<_n) n*=2;
dat=vector<ll>(2*n-1,LLONG_MIN);
}
//k番目(0-indexed)の値をaに変更
void update(long k, ll a){
k+=n-1;
dat[k]=a;
//更新
while(k>0){
k=(k-1)/2;
dat[k]=max(dat[2*k+1],dat[2*k+2]);
}
}
//内部的に投げられるクエリ
ll _query(long a, long b, long k, long l, long r){
if(r<=a || b<=l) return LLONG_MIN;
if(a<=l && r<=b) return dat[k];
else{
ll vl=_query(a,b,2*k+1,l,(l+r)/2);
ll vr=_query(a,b,2*k+2,(l+r)/2,r);
return max(vl,vr);
}
}
//[a,b)の最大値を求める
ll query(long a, long b){
return _query(a,b,0,0,n);
}
};
int main()
{
int n;
scanf(" %d", &n);
MaxSegTree st(n+1);
vector<int> h(n);
rep(i,n)
{
scanf(" %d", &h[i]);
st.update(i,h[i]);
}
rep(i,n)
{
int ans=0;
// iより左について、rまでは見える
int l=-1, r=i;
while(r-l>1)
{
int m=(l+r)/2;
if(st.query(m,i)<=h[i]) r=m;
else l=m;
}
ans+=i-r;
// iより右について、lまでは見える
l=i, r=n;
while(r-l>1)
{
int m=(l+r)/2;
if(st.query(i,m+1)<=h[i]) l=m;
else r=m;
}
ans+=l-i;
printf("%d\n", ans);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 登山家 |
User |
imulan |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
1954 Byte |
Status |
AC |
Exec Time |
522 ms |
Memory |
3356 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:50:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d", &n);
^
./Main.cpp:56:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d", &h[i]);
^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt |
Subtask2 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
18 ms |
920 KB |
sample_02.txt |
AC |
19 ms |
792 KB |
sample_03.txt |
AC |
17 ms |
924 KB |
subtask1_01.txt |
AC |
17 ms |
924 KB |
subtask1_02.txt |
AC |
19 ms |
916 KB |
subtask1_03.txt |
AC |
20 ms |
924 KB |
subtask1_04.txt |
AC |
23 ms |
992 KB |
subtask1_05.txt |
AC |
20 ms |
920 KB |
subtask1_06.txt |
AC |
22 ms |
920 KB |
subtask1_07.txt |
AC |
19 ms |
924 KB |
subtask1_08.txt |
AC |
26 ms |
924 KB |
subtask1_09.txt |
AC |
24 ms |
924 KB |
subtask1_10.txt |
AC |
21 ms |
924 KB |
subtask1_11.txt |
AC |
21 ms |
924 KB |
subtask1_12.txt |
AC |
26 ms |
992 KB |
subtask1_13.txt |
AC |
23 ms |
924 KB |
subtask1_14.txt |
AC |
20 ms |
916 KB |
subtask1_15.txt |
AC |
28 ms |
968 KB |
subtask1_16.txt |
AC |
28 ms |
924 KB |
subtask1_17.txt |
AC |
26 ms |
924 KB |
subtask1_18.txt |
AC |
27 ms |
920 KB |
subtask1_19.txt |
AC |
28 ms |
924 KB |
subtask2_01.txt |
AC |
286 ms |
2072 KB |
subtask2_02.txt |
AC |
136 ms |
1432 KB |
subtask2_03.txt |
AC |
278 ms |
2076 KB |
subtask2_04.txt |
AC |
299 ms |
2072 KB |
subtask2_05.txt |
AC |
499 ms |
3356 KB |
subtask2_06.txt |
AC |
498 ms |
3312 KB |
subtask2_07.txt |
AC |
500 ms |
3304 KB |
subtask2_08.txt |
AC |
500 ms |
3348 KB |
subtask2_09.txt |
AC |
501 ms |
3352 KB |
subtask2_10.txt |
AC |
499 ms |
3356 KB |
subtask2_11.txt |
AC |
521 ms |
3228 KB |
subtask2_12.txt |
AC |
498 ms |
3272 KB |
subtask2_13.txt |
AC |
497 ms |
3356 KB |
subtask2_14.txt |
AC |
499 ms |
3356 KB |
subtask2_15.txt |
AC |
522 ms |
3352 KB |
subtask2_16.txt |
AC |
500 ms |
3356 KB |
subtask2_17.txt |
AC |
498 ms |
3352 KB |
subtask2_18.txt |
AC |
500 ms |
3300 KB |
subtask2_19.txt |
AC |
521 ms |
3352 KB |
subtask2_20.txt |
AC |
520 ms |
3352 KB |