Submission #2553790
Source Code Expand
#include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <climits> #include <ctime> #include <cassert> using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define all(v) begin(v), end(v) #define pb(a) push_back(a) #define fr first #define sc second #define INF 2000000000 #define int long long int #define X real() #define Y imag() #define EPS (1e-10) #define EQ(a,b) (abs((a) - (b)) < EPS) #define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) ) #define LE(n, m) ((n) < (m) + EPS) #define LEQ(n, m) ((n) <= (m) + EPS) #define GE(n, m) ((n) + EPS > (m)) #define GEQ(n, m) ((n) + EPS >= (m)) typedef vector<int> VI; typedef vector<VI> MAT; typedef pair<int, int> pii; typedef long long ll; int dy[]={0, 0, 1, -1}; int dx[]={1, -1, 0, 0}; int const MOD = 1000000007; int x[100010]; int N, L; signed main() { cin >> N >> L; for(int i=0; i<N; i++) { cin >> x[i]; } bool ok = true; pair<int, int> seg(x[N-1], x[N-1] + L); for(int i=0; ; i++) { int lb = seg.first - L, ub = seg.second - L; if(i % 2 == 1) { // arrive int idx = lower_bound(x, x+N, ub) - x - 1, upd = true; if(idx < 0 || idx >= N) upd = false; if(upd) lb = x[idx]; int lb2 = ub, ub2 = seg.first; int vr = upper_bound(x, x+N, ub2) - x - 1; int vl = lower_bound(x, x+N, lb2) - x - 1; // fprintf(stderr, "vl = %lld, vr = %lld\n", vl, vr); if(vr - vl >= 1) ok = false; } else { // jump int idx = upper_bound(x, x+N, lb) - x, upd = true; if(idx < 0 || idx >= N || ub <= x[idx]) upd = false; if(upd) ub = x[idx]; } if(lb >= ub) ok = false; // printf("seg: (%lld, %lld) -> (%lld, %lld)\n", seg.first, seg.second, lb, ub); seg = make_pair(lb, ub); if(ub <= x[0] || !ok) break; } if(seg.second <= 0) ok = false; cout << (ok ? "YES" : "NO") << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ハードル走 |
User | tsutaj |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2470 Byte |
Status | AC |
Exec Time | 54 ms |
Memory | 1024 KB |
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 | 1 ms | 256 KB |
00_sample_part_00 | AC | 1 ms | 256 KB |
00_sample_part_01 | AC | 1 ms | 256 KB |
00_sample_part_02 | AC | 1 ms | 256 KB |
00_sample_part_03 | AC | 1 ms | 256 KB |
00_sample_part_04 | AC | 1 ms | 256 KB |
00_sample_part_05 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_00 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_01 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_02 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_03 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_04 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_05 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_06 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_07 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_08 | AC | 1 ms | 256 KB |
50_random_NLsmall_part_09 | AC | 1 ms | 256 KB |
50_random_XiNsmall_00 | AC | 1 ms | 256 KB |
50_random_XiNsmall_01 | AC | 1 ms | 256 KB |
50_random_XiNsmall_02 | AC | 1 ms | 256 KB |
50_random_XiNsmall_03 | AC | 1 ms | 256 KB |
50_random_XiNsmall_04 | AC | 1 ms | 256 KB |
50_random_XiNsmall_05 | AC | 1 ms | 256 KB |
50_random_XiNsmall_06 | AC | 1 ms | 256 KB |
50_random_XiNsmall_07 | AC | 1 ms | 256 KB |
50_random_XiNsmall_08 | AC | 1 ms | 256 KB |
50_random_XiNsmall_09 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_00 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_01 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_02 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_03 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_04 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_05 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_06 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_07 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_08 | AC | 1 ms | 256 KB |
50_random_XiNsmall_narrow_part_09 | AC | 1 ms | 256 KB |
50_random_XiNsmall_part_00 | AC | 2 ms | 256 KB |
50_random_XiNsmall_part_01 | AC | 2 ms | 256 KB |
50_random_XiNsmall_part_02 | AC | 1 ms | 256 KB |
50_random_XiNsmall_part_03 | AC | 1 ms | 256 KB |
50_random_XiNsmall_part_04 | AC | 1 ms | 256 KB |
50_random_XiNsmall_part_05 | AC | 1 ms | 256 KB |
50_random_XiNsmall_part_06 | AC | 1 ms | 256 KB |
50_random_XiNsmall_part_07 | AC | 1 ms | 256 KB |
50_random_XiNsmall_part_08 | AC | 1 ms | 256 KB |
50_random_XiNsmall_part_09 | AC | 2 ms | 256 KB |
50_random_Xilarge_00 | AC | 13 ms | 512 KB |
50_random_Xilarge_01 | AC | 7 ms | 384 KB |
50_random_Xilarge_02 | AC | 35 ms | 896 KB |
50_random_Xilarge_03 | AC | 16 ms | 512 KB |
50_random_Xilarge_04 | AC | 7 ms | 384 KB |
50_random_Xilarge_05 | AC | 37 ms | 1024 KB |
50_random_Xilarge_06 | AC | 9 ms | 384 KB |
50_random_Xilarge_07 | AC | 36 ms | 896 KB |
50_random_Xilarge_08 | AC | 24 ms | 768 KB |
50_random_Xilarge_09 | AC | 21 ms | 640 KB |
50_random_Xilarge_narrow_00 | AC | 36 ms | 896 KB |
50_random_Xilarge_narrow_01 | AC | 33 ms | 896 KB |
50_random_Xilarge_narrow_02 | AC | 10 ms | 384 KB |
50_random_Xilarge_narrow_03 | AC | 14 ms | 512 KB |
50_random_Xilarge_narrow_04 | AC | 10 ms | 384 KB |
50_random_Xilarge_narrow_05 | AC | 32 ms | 896 KB |
50_random_Xilarge_narrow_06 | AC | 16 ms | 512 KB |
50_random_Xilarge_narrow_07 | AC | 10 ms | 384 KB |
50_random_Xilarge_narrow_08 | AC | 24 ms | 768 KB |
50_random_Xilarge_narrow_09 | AC | 16 ms | 512 KB |
50_random_x0small_00 | AC | 24 ms | 640 KB |
50_random_x0small_01 | AC | 13 ms | 512 KB |
50_random_x0small_02 | AC | 29 ms | 768 KB |
50_random_x0small_03 | AC | 32 ms | 896 KB |
50_random_x0small_04 | AC | 17 ms | 512 KB |
50_random_x0small_05 | AC | 35 ms | 896 KB |
50_random_x0small_06 | AC | 8 ms | 384 KB |
50_random_x0small_07 | AC | 31 ms | 896 KB |
50_random_x0small_08 | AC | 36 ms | 896 KB |
50_random_x0small_09 | AC | 23 ms | 640 KB |
50_random_x1small_part_00 | AC | 2 ms | 256 KB |
50_random_x1small_part_01 | AC | 2 ms | 256 KB |
50_random_x1small_part_02 | AC | 1 ms | 256 KB |
50_random_x1small_part_03 | AC | 1 ms | 256 KB |
50_random_x1small_part_04 | AC | 1 ms | 256 KB |
50_random_x1small_part_05 | AC | 1 ms | 256 KB |
50_random_x1small_part_06 | AC | 1 ms | 256 KB |
50_random_x1small_part_07 | AC | 2 ms | 256 KB |
50_random_x1small_part_08 | AC | 1 ms | 256 KB |
50_random_x1small_part_09 | AC | 1 ms | 256 KB |
80_hand_09 | AC | 3 ms | 256 KB |
80_hand_10 | AC | 3 ms | 256 KB |
80_hand_part_01 | AC | 1 ms | 256 KB |
80_hand_part_02 | AC | 1 ms | 256 KB |
80_hand_part_03 | AC | 1 ms | 256 KB |
80_hand_part_04 | AC | 1 ms | 256 KB |
80_hand_part_05 | AC | 1 ms | 256 KB |
80_hand_part_06 | AC | 1 ms | 256 KB |
80_hand_part_07 | AC | 1 ms | 256 KB |
80_hand_part_08 | AC | 1 ms | 256 KB |
80_hand_part_11 | AC | 1 ms | 256 KB |
80_hand_part_12 | AC | 1 ms | 256 KB |
90_max_no_00 | AC | 40 ms | 1024 KB |
90_max_no_01 | AC | 40 ms | 1024 KB |
90_max_yes_00 | AC | 54 ms | 1024 KB |
90_max_yes_01 | AC | 53 ms | 1024 KB |
98_challenge_part_00 | AC | 1 ms | 256 KB |
98_challenge_part_01 | AC | 1 ms | 256 KB |
98_challenge_part_02 | AC | 1 ms | 256 KB |
98_challenge_part_03 | AC | 1 ms | 256 KB |
98_challenge_part_04 | AC | 1 ms | 256 KB |
98_challenge_part_05 | AC | 1 ms | 256 KB |