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
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 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