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
AC × 7
AC × 62
AC × 109
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