Submission #3376832
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef pair<ll,P> T; typedef vector<int> vi; typedef vector<ll> vll; #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define LLINF 1000000000000000ll #define sz(x) ((int)(x).size()) #define fi first #define sec second #define all(x) (x).begin(),(x).end() #define sq(x) ((x)*(x)) #define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++) #define EQ(a,b) (abs((a)-(b))<eps) template<class T> void chmin(T& a,const T& b){if(a>b)a=b;} template<class T> void chmax(T& a,const T& b){if(a<b)a=b;} const int SIZE = 1<<17; struct segtree{ ll seg[SIZE*2]; void init(){ for(int i=0;i<SIZE*2;i++)seg[i]=LLINF; } void update(int k,ll x){ k += SIZE-1; seg[k] = x; while(k){ k/=2; seg[k]=min(seg[k*2+1],seg[k*2+2]); } } ll query(int a,int b,int k,int l,int r){ if(r<=a||b<=l)return LLINF; else if(a<=l&&r<=b)return seg[k]; else{ int mid = (l+r)/2; ll lch = query(a,b,k*2+1,l,mid); ll rch = query(a,b,k*2+2,mid,r); return min(lch,rch); } } ll query(int a,int b){ if(a>=b)return LLINF; return query(a,b,0,0,SIZE); } }seg; int N; ll L; ll x[100100]; ll dp[100100]; int main(){ seg.init(); scanf("%d %lld",&N,&L); x[0]=-2; for(int i=1;i<=N;i++){ scanf("%lld",&x[i]); x[i]*=2ll; } x[N+1]=LLINF; L*=2ll; /*for(int i=0;i<=N;i++){ printf("%lld ",x[i]); } printf("\n");*/ seg.update(0,0); for(int i=1;i<=N;i++){ int l = upper_bound(x,x+i,x[i]-L)-x; int r = i; //cout << l << ' ' << r << endl; ll ret = seg.query(l,r); //cout << ret << endl; if(l>0&&x[i]-L!=x[l]){ ret = min(ret,max(seg.query(l-1,l),x[i]-L+1ll)); } if(ret!=LLINF)ret+=2ll*L; //printf("%d : %lld\n",i,ret); if(ret<x[i+1])seg.update(i,ret); } if(seg.query(N,N+1)!=LLINF)printf("YES\n"); else printf("NO\n"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ハードル走 |
User | okura |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2016 Byte |
Status | AC |
Exec Time | 41 ms |
Memory | 3072 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:58:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %lld",&N,&L); ^ ./Main.cpp:61:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld",&x[i]); ^
Judge Result
Set Name | Sample | Small | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 100 / 100 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_06, 00_sample_part_00, 00_sample_part_01, 00_sample_part_02, 00_sample_part_03, 00_sample_part_04, 00_sample_part_05 |
Small | 00_sample_part_00, 00_sample_part_01, 00_sample_part_02, 00_sample_part_03, 00_sample_part_04, 00_sample_part_05, 50_random_NLsmall_part_00, 50_random_NLsmall_part_01, 50_random_NLsmall_part_02, 50_random_NLsmall_part_03, 50_random_NLsmall_part_04, 50_random_NLsmall_part_05, 50_random_NLsmall_part_06, 50_random_NLsmall_part_07, 50_random_NLsmall_part_08, 50_random_NLsmall_part_09, 50_random_XiNsmall_narrow_part_00, 50_random_XiNsmall_narrow_part_01, 50_random_XiNsmall_narrow_part_02, 50_random_XiNsmall_narrow_part_03, 50_random_XiNsmall_narrow_part_04, 50_random_XiNsmall_narrow_part_05, 50_random_XiNsmall_narrow_part_06, 50_random_XiNsmall_narrow_part_07, 50_random_XiNsmall_narrow_part_08, 50_random_XiNsmall_narrow_part_09, 50_random_XiNsmall_part_00, 50_random_XiNsmall_part_01, 50_random_XiNsmall_part_02, 50_random_XiNsmall_part_03, 50_random_XiNsmall_part_04, 50_random_XiNsmall_part_05, 50_random_XiNsmall_part_06, 50_random_XiNsmall_part_07, 50_random_XiNsmall_part_08, 50_random_XiNsmall_part_09, 50_random_x1small_part_00, 50_random_x1small_part_01, 50_random_x1small_part_02, 50_random_x1small_part_03, 50_random_x1small_part_04, 50_random_x1small_part_05, 50_random_x1small_part_06, 50_random_x1small_part_07, 50_random_x1small_part_08, 50_random_x1small_part_09, 80_hand_part_01, 80_hand_part_02, 80_hand_part_03, 80_hand_part_04, 80_hand_part_05, 80_hand_part_06, 80_hand_part_07, 80_hand_part_08, 80_hand_part_11, 80_hand_part_12, 98_challenge_part_00, 98_challenge_part_01, 98_challenge_part_02, 98_challenge_part_03, 98_challenge_part_04, 98_challenge_part_05 |
All | 00_sample_06, 00_sample_part_00, 00_sample_part_01, 00_sample_part_02, 00_sample_part_03, 00_sample_part_04, 00_sample_part_05, 50_random_NLsmall_part_00, 50_random_NLsmall_part_01, 50_random_NLsmall_part_02, 50_random_NLsmall_part_03, 50_random_NLsmall_part_04, 50_random_NLsmall_part_05, 50_random_NLsmall_part_06, 50_random_NLsmall_part_07, 50_random_NLsmall_part_08, 50_random_NLsmall_part_09, 50_random_XiNsmall_00, 50_random_XiNsmall_01, 50_random_XiNsmall_02, 50_random_XiNsmall_03, 50_random_XiNsmall_04, 50_random_XiNsmall_05, 50_random_XiNsmall_06, 50_random_XiNsmall_07, 50_random_XiNsmall_08, 50_random_XiNsmall_09, 50_random_XiNsmall_narrow_part_00, 50_random_XiNsmall_narrow_part_01, 50_random_XiNsmall_narrow_part_02, 50_random_XiNsmall_narrow_part_03, 50_random_XiNsmall_narrow_part_04, 50_random_XiNsmall_narrow_part_05, 50_random_XiNsmall_narrow_part_06, 50_random_XiNsmall_narrow_part_07, 50_random_XiNsmall_narrow_part_08, 50_random_XiNsmall_narrow_part_09, 50_random_XiNsmall_part_00, 50_random_XiNsmall_part_01, 50_random_XiNsmall_part_02, 50_random_XiNsmall_part_03, 50_random_XiNsmall_part_04, 50_random_XiNsmall_part_05, 50_random_XiNsmall_part_06, 50_random_XiNsmall_part_07, 50_random_XiNsmall_part_08, 50_random_XiNsmall_part_09, 50_random_Xilarge_00, 50_random_Xilarge_01, 50_random_Xilarge_02, 50_random_Xilarge_03, 50_random_Xilarge_04, 50_random_Xilarge_05, 50_random_Xilarge_06, 50_random_Xilarge_07, 50_random_Xilarge_08, 50_random_Xilarge_09, 50_random_Xilarge_narrow_00, 50_random_Xilarge_narrow_01, 50_random_Xilarge_narrow_02, 50_random_Xilarge_narrow_03, 50_random_Xilarge_narrow_04, 50_random_Xilarge_narrow_05, 50_random_Xilarge_narrow_06, 50_random_Xilarge_narrow_07, 50_random_Xilarge_narrow_08, 50_random_Xilarge_narrow_09, 50_random_x0small_00, 50_random_x0small_01, 50_random_x0small_02, 50_random_x0small_03, 50_random_x0small_04, 50_random_x0small_05, 50_random_x0small_06, 50_random_x0small_07, 50_random_x0small_08, 50_random_x0small_09, 50_random_x1small_part_00, 50_random_x1small_part_01, 50_random_x1small_part_02, 50_random_x1small_part_03, 50_random_x1small_part_04, 50_random_x1small_part_05, 50_random_x1small_part_06, 50_random_x1small_part_07, 50_random_x1small_part_08, 50_random_x1small_part_09, 80_hand_09, 80_hand_10, 80_hand_part_01, 80_hand_part_02, 80_hand_part_03, 80_hand_part_04, 80_hand_part_05, 80_hand_part_06, 80_hand_part_07, 80_hand_part_08, 80_hand_part_11, 80_hand_part_12, 90_max_no_00, 90_max_no_01, 90_max_yes_00, 90_max_yes_01, 98_challenge_part_00, 98_challenge_part_01, 98_challenge_part_02, 98_challenge_part_03, 98_challenge_part_04, 98_challenge_part_05 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_06 | AC | 2 ms | 2304 KB |
00_sample_part_00 | AC | 2 ms | 2304 KB |
00_sample_part_01 | AC | 2 ms | 2304 KB |
00_sample_part_02 | AC | 2 ms | 2304 KB |
00_sample_part_03 | AC | 2 ms | 2304 KB |
00_sample_part_04 | AC | 2 ms | 2304 KB |
00_sample_part_05 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_00 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_01 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_02 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_03 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_04 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_05 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_06 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_07 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_08 | AC | 2 ms | 2304 KB |
50_random_NLsmall_part_09 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_00 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_01 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_02 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_03 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_04 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_05 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_06 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_07 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_08 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_09 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_00 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_01 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_02 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_03 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_04 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_05 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_06 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_07 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_08 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_narrow_part_09 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_00 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_01 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_02 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_03 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_04 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_05 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_06 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_07 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_08 | AC | 2 ms | 2304 KB |
50_random_XiNsmall_part_09 | AC | 2 ms | 2304 KB |
50_random_Xilarge_00 | AC | 9 ms | 2560 KB |
50_random_Xilarge_01 | AC | 5 ms | 2432 KB |
50_random_Xilarge_02 | AC | 32 ms | 2944 KB |
50_random_Xilarge_03 | AC | 16 ms | 2560 KB |
50_random_Xilarge_04 | AC | 6 ms | 2432 KB |
50_random_Xilarge_05 | AC | 36 ms | 3072 KB |
50_random_Xilarge_06 | AC | 7 ms | 2432 KB |
50_random_Xilarge_07 | AC | 35 ms | 2944 KB |
50_random_Xilarge_08 | AC | 19 ms | 2816 KB |
50_random_Xilarge_09 | AC | 16 ms | 2688 KB |
50_random_Xilarge_narrow_00 | AC | 27 ms | 2944 KB |
50_random_Xilarge_narrow_01 | AC | 35 ms | 2944 KB |
50_random_Xilarge_narrow_02 | AC | 8 ms | 2432 KB |
50_random_Xilarge_narrow_03 | AC | 10 ms | 2560 KB |
50_random_Xilarge_narrow_04 | AC | 10 ms | 2432 KB |
50_random_Xilarge_narrow_05 | AC | 31 ms | 2944 KB |
50_random_Xilarge_narrow_06 | AC | 15 ms | 2560 KB |
50_random_Xilarge_narrow_07 | AC | 10 ms | 2432 KB |
50_random_Xilarge_narrow_08 | AC | 24 ms | 2816 KB |
50_random_Xilarge_narrow_09 | AC | 11 ms | 2560 KB |
50_random_x0small_00 | AC | 19 ms | 2816 KB |
50_random_x0small_01 | AC | 13 ms | 2560 KB |
50_random_x0small_02 | AC | 29 ms | 2816 KB |
50_random_x0small_03 | AC | 27 ms | 2944 KB |
50_random_x0small_04 | AC | 17 ms | 2688 KB |
50_random_x0small_05 | AC | 29 ms | 2944 KB |
50_random_x0small_06 | AC | 8 ms | 2432 KB |
50_random_x0small_07 | AC | 26 ms | 2944 KB |
50_random_x0small_08 | AC | 27 ms | 2944 KB |
50_random_x0small_09 | AC | 18 ms | 2688 KB |
50_random_x1small_part_00 | AC | 2 ms | 2304 KB |
50_random_x1small_part_01 | AC | 2 ms | 2304 KB |
50_random_x1small_part_02 | AC | 2 ms | 2304 KB |
50_random_x1small_part_03 | AC | 2 ms | 2304 KB |
50_random_x1small_part_04 | AC | 2 ms | 2304 KB |
50_random_x1small_part_05 | AC | 2 ms | 2304 KB |
50_random_x1small_part_06 | AC | 2 ms | 2304 KB |
50_random_x1small_part_07 | AC | 2 ms | 2304 KB |
50_random_x1small_part_08 | AC | 2 ms | 2304 KB |
50_random_x1small_part_09 | AC | 2 ms | 2304 KB |
80_hand_09 | AC | 3 ms | 2304 KB |
80_hand_10 | AC | 3 ms | 2304 KB |
80_hand_part_01 | AC | 2 ms | 2304 KB |
80_hand_part_02 | AC | 2 ms | 2304 KB |
80_hand_part_03 | AC | 2 ms | 2304 KB |
80_hand_part_04 | AC | 2 ms | 2304 KB |
80_hand_part_05 | AC | 2 ms | 2304 KB |
80_hand_part_06 | AC | 2 ms | 2304 KB |
80_hand_part_07 | AC | 2 ms | 2304 KB |
80_hand_part_08 | AC | 2 ms | 2304 KB |
80_hand_part_11 | AC | 2 ms | 2304 KB |
80_hand_part_12 | AC | 2 ms | 2304 KB |
90_max_no_00 | AC | 41 ms | 3072 KB |
90_max_no_01 | AC | 39 ms | 3072 KB |
90_max_yes_00 | AC | 27 ms | 3072 KB |
90_max_yes_01 | AC | 27 ms | 3072 KB |
98_challenge_part_00 | AC | 2 ms | 2304 KB |
98_challenge_part_01 | AC | 2 ms | 2304 KB |
98_challenge_part_02 | AC | 2 ms | 2304 KB |
98_challenge_part_03 | AC | 2 ms | 2304 KB |
98_challenge_part_04 | AC | 2 ms | 2304 KB |
98_challenge_part_05 | AC | 2 ms | 2304 KB |