Submission #101813


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100010;
const int MAX_LOG_N = 17;
int N, M;
int s[MAX_N*2], t[MAX_N*2];

pair<int,int> ps[MAX_N*4];
int next_dp[MAX_LOG_N][MAX_N*2];

void solve() {
    int res = 0;
    for(int i = 0; i < N; ++i) {
        if(t[i] < s[i]) t[i] += M;
        s[N+i] = s[i]+M;
        t[N+i] = t[i]+M;
    }

    for(int i = 0; i < N*2; ++i) {
        ps[i] = make_pair(t[i], i);
        ps[N*2+i] = make_pair(s[i], N*2+i);
    }
    sort(ps, ps+N*4);

    int last = -1;
    for(int i = N*4-1; i >= 0; --i) {
        int id = ps[i].second;
        if(id < N*2) {
            next_dp[0][id] = last;
        } else {
            id -= N*2;
            if(last < 0 || t[last] > t[id]) {
                last = id;
            }
        }
    }

    for(int k = 0; k+1 < MAX_LOG_N; ++k) {
        for(int i = 0; i < N*2; ++i) {
            if(next_dp[k][i] < 0) next_dp[k+1][i] = -1;
            else next_dp[k+1][i] = next_dp[k][next_dp[k][i]];
        }
    }

    for(int i = 0; i < N; ++i) {
        int tmp = 0, j = i;
        for(int k = MAX_LOG_N-1; k >= 0; --k) {
            int j2 = next_dp[k][j];
            if(j2 >= 0 && t[j2] <= s[i]+M) {
                j = j2;
                tmp |= 1 << k;
            }
        }
        res = max(res, tmp+1);
    }
    cout << res << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> N >> M;
    for(int i = 0; i < N; ++i) {
        cin >> s[i] >> t[i];
    }
    solve();
    return 0;
}

Submission Info

Submission Time
Task A - Anime Master
User binding_pry
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1622 Byte
Status AC
Exec Time 194 ms
Memory 18728 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 89
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 5, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 6, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 7, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 8, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 9
Case Name Status Exec Time Memory
1 AC 27 ms 4008 KB
10 AC 24 ms 3996 KB
11 AC 24 ms 3984 KB
12 AC 27 ms 4004 KB
13 AC 26 ms 4004 KB
14 AC 26 ms 4004 KB
15 AC 26 ms 4000 KB
16 AC 25 ms 3992 KB
17 AC 26 ms 4004 KB
18 AC 26 ms 4132 KB
19 AC 26 ms 4004 KB
2 AC 28 ms 3960 KB
20 AC 26 ms 4012 KB
21 AC 26 ms 4004 KB
22 AC 26 ms 3960 KB
23 AC 26 ms 4008 KB
24 AC 26 ms 4008 KB
25 AC 25 ms 4004 KB
26 AC 26 ms 4004 KB
27 AC 25 ms 3996 KB
28 AC 26 ms 4016 KB
29 AC 26 ms 4000 KB
3 AC 26 ms 4012 KB
30 AC 26 ms 4000 KB
31 AC 26 ms 4000 KB
32 AC 26 ms 3960 KB
33 AC 24 ms 4000 KB
34 AC 26 ms 3996 KB
35 AC 26 ms 3996 KB
36 AC 26 ms 4004 KB
37 AC 26 ms 3948 KB
38 AC 26 ms 4004 KB
39 AC 26 ms 4012 KB
4 AC 26 ms 4008 KB
40 AC 25 ms 4000 KB
41 AC 26 ms 4020 KB
42 AC 26 ms 4000 KB
43 AC 26 ms 4000 KB
44 AC 27 ms 3940 KB
45 AC 25 ms 3992 KB
46 AC 26 ms 4004 KB
47 AC 26 ms 4128 KB
48 AC 25 ms 4012 KB
49 AC 26 ms 4004 KB
5 AC 26 ms 4000 KB
50 AC 26 ms 4084 KB
51 AC 26 ms 4008 KB
52 AC 25 ms 4112 KB
53 AC 26 ms 4008 KB
54 AC 26 ms 4128 KB
55 AC 25 ms 4012 KB
56 AC 26 ms 4008 KB
57 AC 26 ms 4012 KB
58 AC 156 ms 18728 KB
59 AC 161 ms 18724 KB
6 AC 26 ms 4136 KB
60 AC 141 ms 18728 KB
61 AC 149 ms 18728 KB
62 AC 155 ms 18724 KB
63 AC 155 ms 18724 KB
64 AC 194 ms 18720 KB
65 AC 61 ms 8112 KB
66 AC 98 ms 11816 KB
67 AC 65 ms 8348 KB
68 AC 31 ms 4772 KB
69 AC 27 ms 4132 KB
7 AC 26 ms 3996 KB
70 AC 31 ms 4392 KB
71 AC 25 ms 4000 KB
72 AC 27 ms 4088 KB
73 AC 26 ms 4004 KB
74 AC 28 ms 4336 KB
75 AC 30 ms 4648 KB
76 AC 34 ms 5156 KB
77 AC 31 ms 4636 KB
78 AC 33 ms 5032 KB
79 AC 29 ms 4260 KB
8 AC 26 ms 3996 KB
80 AC 27 ms 4384 KB
81 AC 33 ms 4840 KB
82 AC 31 ms 4896 KB
83 AC 29 ms 4624 KB
84 AC 37 ms 5416 KB
85 AC 36 ms 5348 KB
86 AC 29 ms 4508 KB
87 AC 32 ms 4780 KB
88 AC 30 ms 4772 KB
89 AC 36 ms 5408 KB
9 AC 24 ms 4008 KB