oj.uz

Submission #972977

# Submission time Handle Problem Language Result Execution time Memory
972977 2024-05-01T11:08:54 Z Gajowy Event Hopping 2 (JOI21_event2) C++17
100 / 100
 151 ms 25544 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fwd(i, a, n) for (int i = (a); i < (n); i ++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) begin(X), end(X)
#define sz(X) ((int)X.size())
#define st first
#define nd second
#define vi vector<int>
#define pii pair<int, int>
#define ll long long
#define vll vector<long long>

#ifdef LOC
auto &operator<<(auto &out, pair<auto, auto> a) {
    return out << "(" << a.st << ", " << a.nd << ")";
}
auto &operator<<(auto &out, auto a) {
    out << "{";
    for (auto b : a)
        out << b << ", ";
    return out << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif

const int inf = 2e9;
const int LG = 20;

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, k;
    cin >> n >> k;
    vi l(n + 2), r(n + 2);
    vector<vi> jmp(LG, vi(n + 2));
    jmp[0][n + 1] = n + 1;
    l[n + 1] = inf;
    r[n + 1] = inf + 1;
    l[n] = -1;
    r[n] = 0;
    vector<array<int, 3> > a(n + 1);
    rep(i, n) {
        cin >> l[i] >> r[i];
        a[i] = {l[i], r[i], i};
    }
    a[n] = {l[n], r[n], n};
    sort(all(a), greater<array<int, 3> >());
    map<int, pii> dp;
    dp[l[n + 1]] = {r[n + 1], n + 1};
    for (auto [x, y, id] : a) {
        jmp[0][id] = dp.lower_bound(y)->nd.nd;
        dp[x] = min(make_pair(y, id), dp.lower_bound(x)->nd);
    }
    debug(jmp[0]);
    fwd(i, 1, LG)
        rep(j, n + 2)
            jmp[i][j] = jmp[i - 1][jmp[i - 1][j]];
    auto most = [&] (int v, int R) {
        int ans = 0;
        for (int i = LG - 1; i >= 0; i --)
            if (r[jmp[i][v]] <= R) {
                ans += (1 << i);
                v = jmp[i][v];
                debug(v);
            }
        return ans;
    };
    set<array<int, 3> > odp;
    odp.insert({l[n], r[n], n});
    odp.insert({l[n + 1], r[n + 1], n + 1});
    int S = most(n, inf - 1);
    if (S < k) {
        cout << "-1\n";
        return 0;
    }
    vi take(n, 0);
    rep(i, n) {
        auto nxt = odp.lower_bound({l[i], -1, -1});
        if ((*nxt)[0] < r[i]) continue;
        int R = (*nxt)[0];
        nxt --;
        if ((*nxt)[1] > l[i]) continue;
        int L = (*nxt)[1];
        int pid = (*nxt)[2];
        int will_have = S + most(pid, l[i]) + most(i, R) - most(pid, R);
        if (will_have < k - 1) continue;
        take[i] = 1;
        odp.insert({l[i], r[i], i});
        S = will_have;
        k --;
        if (k == 0) break;
    }
    rep(i, n)
        if (take[i])
            cout << i + 1 << "\n";
}

Compilation message

event2.cpp: In function 'int32_t main()':
event2.cpp:29:20: warning: statement has no effect [-Wunused-value]
   29 | #define debug(...) 0
      |                    ^
event2.cpp:59:5: note: in expansion of macro 'debug'
   59 |     debug(jmp[0]);
      |     ^~~~~
event2.cpp: In lambda function:
event2.cpp:29:20: warning: statement has no effect [-Wunused-value]
   29 | #define debug(...) 0
      |                    ^
event2.cpp:69:17: note: in expansion of macro 'debug'
   69 |                 debug(v);
      |                 ^~~~~
event2.cpp: In function 'int32_t main()':
event2.cpp:88:13: warning: unused variable 'L' [-Wunused-variable]
   88 |         int L = (*nxt)[1];
      |             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 119 ms 23072 KB Output is correct
5 Correct 123 ms 24768 KB Output is correct
6 Correct 118 ms 24440 KB Output is correct
7 Correct 104 ms 23816 KB Output is correct
8 Correct 119 ms 25000 KB Output is correct
9 Correct 121 ms 24876 KB Output is correct
10 Correct 111 ms 24492 KB Output is correct
11 Correct 116 ms 23944 KB Output is correct
12 Correct 120 ms 22728 KB Output is correct
13 Correct 107 ms 22476 KB Output is correct
14 Correct 103 ms 22236 KB Output is correct
15 Correct 102 ms 21960 KB Output is correct
16 Correct 77 ms 19732 KB Output is correct
17 Correct 76 ms 19400 KB Output is correct
18 Correct 78 ms 19400 KB Output is correct
19 Correct 76 ms 18892 KB Output is correct
20 Correct 70 ms 18852 KB Output is correct
21 Correct 72 ms 18864 KB Output is correct
22 Correct 70 ms 18632 KB Output is correct
23 Correct 70 ms 18848 KB Output is correct
24 Correct 72 ms 18644 KB Output is correct
25 Correct 77 ms 18680 KB Output is correct
26 Correct 70 ms 18624 KB Output is correct
27 Correct 75 ms 18816 KB Output is correct
28 Correct 66 ms 18376 KB Output is correct
29 Correct 65 ms 18436 KB Output is correct
30 Correct 68 ms 18376 KB Output is correct
31 Correct 71 ms 18388 KB Output is correct
32 Correct 69 ms 18380 KB Output is correct
33 Correct 69 ms 18404 KB Output is correct
34 Correct 84 ms 21176 KB Output is correct
35 Correct 77 ms 20424 KB Output is correct
36 Correct 80 ms 19608 KB Output is correct
37 Correct 96 ms 22216 KB Output is correct
38 Correct 103 ms 21960 KB Output is correct
39 Correct 99 ms 22092 KB Output is correct
40 Correct 95 ms 21704 KB Output is correct
41 Correct 91 ms 21712 KB Output is correct
42 Correct 68 ms 18336 KB Output is correct
43 Correct 105 ms 21928 KB Output is correct
44 Correct 98 ms 21960 KB Output is correct
45 Correct 94 ms 21708 KB Output is correct
46 Correct 92 ms 21704 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 416 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 460 KB Output is correct
27 Correct 0 ms 348 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 416 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 460 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 3 ms 1136 KB Output is correct
29 Correct 2 ms 856 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 2 ms 980 KB Output is correct
32 Correct 2 ms 860 KB Output is correct
33 Correct 2 ms 820 KB Output is correct
34 Correct 2 ms 860 KB Output is correct
35 Correct 3 ms 1116 KB Output is correct
36 Correct 3 ms 1116 KB Output is correct
37 Correct 2 ms 1116 KB Output is correct
38 Correct 2 ms 860 KB Output is correct
39 Correct 3 ms 1116 KB Output is correct
40 Correct 3 ms 1116 KB Output is correct
41 Correct 3 ms 980 KB Output is correct
42 Correct 2 ms 860 KB Output is correct
43 Correct 3 ms 1236 KB Output is correct
44 Correct 2 ms 860 KB Output is correct
45 Correct 2 ms 860 KB Output is correct
46 Correct 2 ms 860 KB Output is correct
47 Correct 2 ms 824 KB Output is correct
48 Correct 2 ms 856 KB Output is correct
49 Correct 2 ms 824 KB Output is correct
50 Correct 2 ms 1112 KB Output is correct
51 Correct 2 ms 860 KB Output is correct
52 Correct 2 ms 856 KB Output is correct
53 Correct 2 ms 856 KB Output is correct
54 Correct 2 ms 860 KB Output is correct
55 Correct 3 ms 1112 KB Output is correct
56 Correct 3 ms 1116 KB Output is correct
57 Correct 3 ms 1116 KB Output is correct
58 Correct 3 ms 1116 KB Output is correct
59 Correct 3 ms 1116 KB Output is correct
60 Correct 2 ms 1116 KB Output is correct
61 Correct 3 ms 1116 KB Output is correct
62 Correct 3 ms 1116 KB Output is correct
63 Correct 3 ms 1116 KB Output is correct
64 Correct 2 ms 860 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 119 ms 23072 KB Output is correct
5 Correct 123 ms 24768 KB Output is correct
6 Correct 118 ms 24440 KB Output is correct
7 Correct 104 ms 23816 KB Output is correct
8 Correct 119 ms 25000 KB Output is correct
9 Correct 121 ms 24876 KB Output is correct
10 Correct 111 ms 24492 KB Output is correct
11 Correct 116 ms 23944 KB Output is correct
12 Correct 120 ms 22728 KB Output is correct
13 Correct 107 ms 22476 KB Output is correct
14 Correct 103 ms 22236 KB Output is correct
15 Correct 102 ms 21960 KB Output is correct
16 Correct 77 ms 19732 KB Output is correct
17 Correct 76 ms 19400 KB Output is correct
18 Correct 78 ms 19400 KB Output is correct
19 Correct 76 ms 18892 KB Output is correct
20 Correct 70 ms 18852 KB Output is correct
21 Correct 72 ms 18864 KB Output is correct
22 Correct 70 ms 18632 KB Output is correct
23 Correct 70 ms 18848 KB Output is correct
24 Correct 72 ms 18644 KB Output is correct
25 Correct 77 ms 18680 KB Output is correct
26 Correct 70 ms 18624 KB Output is correct
27 Correct 75 ms 18816 KB Output is correct
28 Correct 66 ms 18376 KB Output is correct
29 Correct 65 ms 18436 KB Output is correct
30 Correct 68 ms 18376 KB Output is correct
31 Correct 71 ms 18388 KB Output is correct
32 Correct 69 ms 18380 KB Output is correct
33 Correct 69 ms 18404 KB Output is correct
34 Correct 84 ms 21176 KB Output is correct
35 Correct 77 ms 20424 KB Output is correct
36 Correct 80 ms 19608 KB Output is correct
37 Correct 96 ms 22216 KB Output is correct
38 Correct 103 ms 21960 KB Output is correct
39 Correct 99 ms 22092 KB Output is correct
40 Correct 95 ms 21704 KB Output is correct
41 Correct 91 ms 21712 KB Output is correct
42 Correct 68 ms 18336 KB Output is correct
43 Correct 105 ms 21928 KB Output is correct
44 Correct 98 ms 21960 KB Output is correct
45 Correct 94 ms 21708 KB Output is correct
46 Correct 92 ms 21704 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 1 ms 344 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 416 KB Output is correct
62 Correct 0 ms 344 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 0 ms 348 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 0 ms 344 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 0 ms 348 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 0 ms 460 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 3 ms 1136 KB Output is correct
75 Correct 2 ms 856 KB Output is correct
76 Correct 2 ms 860 KB Output is correct
77 Correct 2 ms 980 KB Output is correct
78 Correct 2 ms 860 KB Output is correct
79 Correct 2 ms 820 KB Output is correct
80 Correct 2 ms 860 KB Output is correct
81 Correct 3 ms 1116 KB Output is correct
82 Correct 3 ms 1116 KB Output is correct
83 Correct 2 ms 1116 KB Output is correct
84 Correct 2 ms 860 KB Output is correct
85 Correct 3 ms 1116 KB Output is correct
86 Correct 3 ms 1116 KB Output is correct
87 Correct 3 ms 980 KB Output is correct
88 Correct 2 ms 860 KB Output is correct
89 Correct 3 ms 1236 KB Output is correct
90 Correct 2 ms 860 KB Output is correct
91 Correct 2 ms 860 KB Output is correct
92 Correct 2 ms 860 KB Output is correct
93 Correct 2 ms 824 KB Output is correct
94 Correct 2 ms 856 KB Output is correct
95 Correct 2 ms 824 KB Output is correct
96 Correct 2 ms 1112 KB Output is correct
97 Correct 2 ms 860 KB Output is correct
98 Correct 2 ms 856 KB Output is correct
99 Correct 2 ms 856 KB Output is correct
100 Correct 2 ms 860 KB Output is correct
101 Correct 3 ms 1112 KB Output is correct
102 Correct 3 ms 1116 KB Output is correct
103 Correct 3 ms 1116 KB Output is correct
104 Correct 3 ms 1116 KB Output is correct
105 Correct 3 ms 1116 KB Output is correct
106 Correct 2 ms 1116 KB Output is correct
107 Correct 3 ms 1116 KB Output is correct
108 Correct 3 ms 1116 KB Output is correct
109 Correct 3 ms 1116 KB Output is correct
110 Correct 2 ms 860 KB Output is correct
111 Correct 80 ms 18876 KB Output is correct
112 Correct 83 ms 18632 KB Output is correct
113 Correct 77 ms 18848 KB Output is correct
114 Correct 75 ms 18676 KB Output is correct
115 Correct 77 ms 18840 KB Output is correct
116 Correct 78 ms 18348 KB Output is correct
117 Correct 71 ms 18380 KB Output is correct
118 Correct 142 ms 25168 KB Output is correct
119 Correct 135 ms 24480 KB Output is correct
120 Correct 113 ms 22176 KB Output is correct
121 Correct 60 ms 18376 KB Output is correct
122 Correct 113 ms 22732 KB Output is correct
123 Correct 108 ms 22220 KB Output is correct
124 Correct 102 ms 22080 KB Output is correct
125 Correct 60 ms 18380 KB Output is correct
126 Correct 86 ms 19656 KB Output is correct
127 Correct 81 ms 19604 KB Output is correct
128 Correct 86 ms 19404 KB Output is correct
129 Correct 70 ms 18424 KB Output is correct
130 Correct 73 ms 18892 KB Output is correct
131 Correct 71 ms 18892 KB Output is correct
132 Correct 78 ms 18696 KB Output is correct
133 Correct 64 ms 18380 KB Output is correct
134 Correct 74 ms 18636 KB Output is correct
135 Correct 68 ms 18756 KB Output is correct
136 Correct 69 ms 18708 KB Output is correct
137 Correct 72 ms 18380 KB Output is correct
138 Correct 68 ms 18636 KB Output is correct
139 Correct 67 ms 18632 KB Output is correct
140 Correct 66 ms 18864 KB Output is correct
141 Correct 64 ms 18308 KB Output is correct
142 Correct 151 ms 25508 KB Output is correct
143 Correct 122 ms 25544 KB Output is correct
144 Correct 127 ms 25492 KB Output is correct
145 Correct 113 ms 25396 KB Output is correct
146 Correct 113 ms 25260 KB Output is correct
147 Correct 115 ms 25372 KB Output is correct
148 Correct 115 ms 25024 KB Output is correct
149 Correct 112 ms 25036 KB Output is correct
150 Correct 121 ms 24908 KB Output is correct
151 Correct 108 ms 24256 KB Output is correct
152 Correct 70 ms 18380 KB Output is correct
153 Correct 121 ms 25492 KB Output is correct
154 Correct 115 ms 25496 KB Output is correct
155 Correct 120 ms 25260 KB Output is correct
156 Correct 108 ms 25072 KB Output is correct
157 Correct 109 ms 25072 KB Output is correct
158 Correct 99 ms 24952 KB Output is correct
159 Correct 117 ms 24104 KB Output is correct
160 Correct 72 ms 18328 KB Output is correct
161 Correct 108 ms 22040 KB Output is correct
162 Correct 103 ms 22048 KB Output is correct
163 Correct 103 ms 22060 KB Output is correct
164 Correct 100 ms 21696 KB Output is correct
165 Correct 97 ms 21704 KB Output is correct
166 Correct 72 ms 18380 KB Output is correct
167 Correct 101 ms 22080 KB Output is correct
168 Correct 99 ms 21816 KB Output is correct
169 Correct 96 ms 21708 KB Output is correct
170 Correct 87 ms 21712 KB Output is correct
171 Correct 82 ms 21452 KB Output is correct
172 Correct 95 ms 22312 KB Output is correct
173 Correct 110 ms 22204 KB Output is correct
174 Correct 114 ms 22216 KB Output is correct
175 Correct 113 ms 22168 KB Output is correct
176 Correct 100 ms 21516 KB Output is correct