# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
389727 | 2021-04-14T12:13:13 Z | georgerapeanu | Event Hopping 2 (JOI21_event2) | C++11 | 361 ms | 38120 KB |
#include <bits/stdc++.h> using namespace std; const int LGMAX = 17; const int NMAX = 1e5; int n,k; map<int,int> to_norm; int skip_list[LGMAX + 1 + 1][2 * NMAX + 5]; pair<int,int> v[NMAX + 5]; int closest_endpoint[2 * NMAX + 5]; int get_segment_count(int l,int r){ if(l > r){ return 0; } int ans = 0; for(int h = LGMAX;h >= 0;h--){ if(skip_list[h][l] != 0 && skip_list[h][l] <= r + 1){ ans += (1 << h); l = skip_list[h][l]; } } return ans; } int aib[2 * NMAX + 5]; void update(int pos){ for(;pos <= 2 * n + 3;pos += (-pos) & pos){ aib[pos] ^= 1; } } int query(int pos){ int ans = 0; for(;pos;pos -= (-pos) & pos){ ans ^= aib[pos]; } return ans; } set<int> pos; int main(){ scanf("%d %d",&n,&k); for(int i = 1;i <= n;i++){ scanf("%d %d",&v[i].first,&v[i].second); v[i].second--; to_norm[v[i].first] = 1; to_norm[v[i].second] = 1; } int lst = 0; for(auto &it:to_norm){ it.second = ++lst; } for(int i = 1;i <= lst + 1;i++){ closest_endpoint[i] = 1e9; } for(int i = 1;i <= n;i++){ v[i].first = to_norm[v[i].first]; v[i].second = to_norm[v[i].second]; closest_endpoint[v[i].first] = min(closest_endpoint[v[i].first],v[i].second); } for(int i = lst;i;i--){ skip_list[0][i] = skip_list[0][i + 1]; if(closest_endpoint[i] != 1e9 && (skip_list[0][i] == 0 || closest_endpoint[i] + 1 < skip_list[0][i])){ skip_list[0][i] = closest_endpoint[i] + 1; } } for(int h = 1;h <= LGMAX;h++){ for(int i = 1;i <= lst;i++){ skip_list[h][i] = skip_list[h - 1][skip_list[h - 1][i]]; } } pos.insert(0); pos.insert(2 * n + 3); int ans = get_segment_count(1,2 * n + 2); if(ans < k){ printf("-1\n"); return 0; } for(int i = 1;i <= n;i++){ set<int> :: iterator it; it = pos.lower_bound(v[i].first); if(*it <= v[i].second || query(v[i].first)){ continue; } int r = *it - 1; it--; int l = *it + 1; int local_ans = ans - get_segment_count(l,r) + get_segment_count(l,v[i].first - 1) + get_segment_count(v[i].second + 1,r); if(k > 0 && local_ans >= k - 1){ k--; ans = local_ans; printf("%d\n",i); pos.insert(v[i].first); pos.insert(v[i].second); update(v[i].first); update(v[i].second + 1); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 336 KB | Output is correct |
4 | Correct | 188 ms | 35552 KB | Output is correct |
5 | Correct | 180 ms | 36804 KB | Output is correct |
6 | Correct | 177 ms | 36292 KB | Output is correct |
7 | Correct | 177 ms | 35320 KB | Output is correct |
8 | Correct | 183 ms | 37312 KB | Output is correct |
9 | Correct | 179 ms | 36796 KB | Output is correct |
10 | Correct | 184 ms | 36384 KB | Output is correct |
11 | Correct | 173 ms | 35236 KB | Output is correct |
12 | Correct | 150 ms | 33656 KB | Output is correct |
13 | Correct | 151 ms | 33384 KB | Output is correct |
14 | Correct | 151 ms | 33112 KB | Output is correct |
15 | Correct | 149 ms | 32460 KB | Output is correct |
16 | Correct | 112 ms | 29220 KB | Output is correct |
17 | Correct | 112 ms | 29092 KB | Output is correct |
18 | Correct | 114 ms | 28920 KB | Output is correct |
19 | Correct | 106 ms | 28304 KB | Output is correct |
20 | Correct | 110 ms | 28076 KB | Output is correct |
21 | Correct | 104 ms | 28100 KB | Output is correct |
22 | Correct | 113 ms | 28148 KB | Output is correct |
23 | Correct | 112 ms | 28012 KB | Output is correct |
24 | Correct | 112 ms | 28032 KB | Output is correct |
25 | Correct | 133 ms | 27400 KB | Output is correct |
26 | Correct | 134 ms | 27444 KB | Output is correct |
27 | Correct | 130 ms | 27444 KB | Output is correct |
28 | Correct | 101 ms | 27244 KB | Output is correct |
29 | Correct | 89 ms | 27204 KB | Output is correct |
30 | Correct | 92 ms | 27236 KB | Output is correct |
31 | Correct | 100 ms | 27268 KB | Output is correct |
32 | Correct | 110 ms | 27280 KB | Output is correct |
33 | Correct | 169 ms | 27172 KB | Output is correct |
34 | Correct | 146 ms | 31172 KB | Output is correct |
35 | Correct | 131 ms | 29828 KB | Output is correct |
36 | Correct | 126 ms | 28700 KB | Output is correct |
37 | Correct | 151 ms | 32964 KB | Output is correct |
38 | Correct | 154 ms | 32772 KB | Output is correct |
39 | Correct | 152 ms | 32580 KB | Output is correct |
40 | Correct | 148 ms | 32452 KB | Output is correct |
41 | Correct | 147 ms | 32068 KB | Output is correct |
42 | Correct | 95 ms | 27220 KB | Output is correct |
43 | Correct | 173 ms | 32760 KB | Output is correct |
44 | Correct | 141 ms | 32588 KB | Output is correct |
45 | Correct | 136 ms | 32324 KB | Output is correct |
46 | Correct | 132 ms | 32068 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 460 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 336 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 1 ms | 332 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 1 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 1 ms | 332 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 332 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
21 | Correct | 1 ms | 336 KB | Output is correct |
22 | Correct | 1 ms | 332 KB | Output is correct |
23 | Correct | 1 ms | 344 KB | Output is correct |
24 | Correct | 1 ms | 332 KB | Output is correct |
25 | Correct | 1 ms | 336 KB | Output is correct |
26 | Correct | 1 ms | 332 KB | Output is correct |
27 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 460 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 336 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 1 ms | 332 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 1 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 1 ms | 332 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 332 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
21 | Correct | 1 ms | 336 KB | Output is correct |
22 | Correct | 1 ms | 332 KB | Output is correct |
23 | Correct | 1 ms | 344 KB | Output is correct |
24 | Correct | 1 ms | 332 KB | Output is correct |
25 | Correct | 1 ms | 336 KB | Output is correct |
26 | Correct | 1 ms | 332 KB | Output is correct |
27 | Correct | 1 ms | 332 KB | Output is correct |
28 | Correct | 6 ms | 1100 KB | Output is correct |
29 | Correct | 4 ms | 1100 KB | Output is correct |
30 | Correct | 4 ms | 1100 KB | Output is correct |
31 | Correct | 4 ms | 1100 KB | Output is correct |
32 | Correct | 4 ms | 1100 KB | Output is correct |
33 | Correct | 4 ms | 1140 KB | Output is correct |
34 | Correct | 4 ms | 1100 KB | Output is correct |
35 | Correct | 6 ms | 1360 KB | Output is correct |
36 | Correct | 6 ms | 1356 KB | Output is correct |
37 | Correct | 6 ms | 1384 KB | Output is correct |
38 | Correct | 4 ms | 1100 KB | Output is correct |
39 | Correct | 6 ms | 1356 KB | Output is correct |
40 | Correct | 6 ms | 1356 KB | Output is correct |
41 | Correct | 6 ms | 1288 KB | Output is correct |
42 | Correct | 4 ms | 1100 KB | Output is correct |
43 | Correct | 5 ms | 1228 KB | Output is correct |
44 | Correct | 5 ms | 1228 KB | Output is correct |
45 | Correct | 5 ms | 1228 KB | Output is correct |
46 | Correct | 4 ms | 1100 KB | Output is correct |
47 | Correct | 6 ms | 1100 KB | Output is correct |
48 | Correct | 4 ms | 1100 KB | Output is correct |
49 | Correct | 4 ms | 1100 KB | Output is correct |
50 | Correct | 4 ms | 1104 KB | Output is correct |
51 | Correct | 4 ms | 1100 KB | Output is correct |
52 | Correct | 4 ms | 1100 KB | Output is correct |
53 | Correct | 4 ms | 1100 KB | Output is correct |
54 | Correct | 4 ms | 1100 KB | Output is correct |
55 | Correct | 6 ms | 1484 KB | Output is correct |
56 | Correct | 5 ms | 1404 KB | Output is correct |
57 | Correct | 5 ms | 1356 KB | Output is correct |
58 | Correct | 5 ms | 1356 KB | Output is correct |
59 | Correct | 5 ms | 1356 KB | Output is correct |
60 | Correct | 5 ms | 1356 KB | Output is correct |
61 | Correct | 5 ms | 1360 KB | Output is correct |
62 | Correct | 5 ms | 1356 KB | Output is correct |
63 | Correct | 5 ms | 1356 KB | Output is correct |
64 | Correct | 3 ms | 1104 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 336 KB | Output is correct |
4 | Correct | 188 ms | 35552 KB | Output is correct |
5 | Correct | 180 ms | 36804 KB | Output is correct |
6 | Correct | 177 ms | 36292 KB | Output is correct |
7 | Correct | 177 ms | 35320 KB | Output is correct |
8 | Correct | 183 ms | 37312 KB | Output is correct |
9 | Correct | 179 ms | 36796 KB | Output is correct |
10 | Correct | 184 ms | 36384 KB | Output is correct |
11 | Correct | 173 ms | 35236 KB | Output is correct |
12 | Correct | 150 ms | 33656 KB | Output is correct |
13 | Correct | 151 ms | 33384 KB | Output is correct |
14 | Correct | 151 ms | 33112 KB | Output is correct |
15 | Correct | 149 ms | 32460 KB | Output is correct |
16 | Correct | 112 ms | 29220 KB | Output is correct |
17 | Correct | 112 ms | 29092 KB | Output is correct |
18 | Correct | 114 ms | 28920 KB | Output is correct |
19 | Correct | 106 ms | 28304 KB | Output is correct |
20 | Correct | 110 ms | 28076 KB | Output is correct |
21 | Correct | 104 ms | 28100 KB | Output is correct |
22 | Correct | 113 ms | 28148 KB | Output is correct |
23 | Correct | 112 ms | 28012 KB | Output is correct |
24 | Correct | 112 ms | 28032 KB | Output is correct |
25 | Correct | 133 ms | 27400 KB | Output is correct |
26 | Correct | 134 ms | 27444 KB | Output is correct |
27 | Correct | 130 ms | 27444 KB | Output is correct |
28 | Correct | 101 ms | 27244 KB | Output is correct |
29 | Correct | 89 ms | 27204 KB | Output is correct |
30 | Correct | 92 ms | 27236 KB | Output is correct |
31 | Correct | 100 ms | 27268 KB | Output is correct |
32 | Correct | 110 ms | 27280 KB | Output is correct |
33 | Correct | 169 ms | 27172 KB | Output is correct |
34 | Correct | 146 ms | 31172 KB | Output is correct |
35 | Correct | 131 ms | 29828 KB | Output is correct |
36 | Correct | 126 ms | 28700 KB | Output is correct |
37 | Correct | 151 ms | 32964 KB | Output is correct |
38 | Correct | 154 ms | 32772 KB | Output is correct |
39 | Correct | 152 ms | 32580 KB | Output is correct |
40 | Correct | 148 ms | 32452 KB | Output is correct |
41 | Correct | 147 ms | 32068 KB | Output is correct |
42 | Correct | 95 ms | 27220 KB | Output is correct |
43 | Correct | 173 ms | 32760 KB | Output is correct |
44 | Correct | 141 ms | 32588 KB | Output is correct |
45 | Correct | 136 ms | 32324 KB | Output is correct |
46 | Correct | 132 ms | 32068 KB | Output is correct |
47 | Correct | 0 ms | 332 KB | Output is correct |
48 | Correct | 1 ms | 332 KB | Output is correct |
49 | Correct | 1 ms | 332 KB | Output is correct |
50 | Correct | 1 ms | 460 KB | Output is correct |
51 | Correct | 1 ms | 332 KB | Output is correct |
52 | Correct | 1 ms | 332 KB | Output is correct |
53 | Correct | 1 ms | 332 KB | Output is correct |
54 | Correct | 1 ms | 336 KB | Output is correct |
55 | Correct | 1 ms | 332 KB | Output is correct |
56 | Correct | 1 ms | 332 KB | Output is correct |
57 | Correct | 0 ms | 332 KB | Output is correct |
58 | Correct | 1 ms | 332 KB | Output is correct |
59 | Correct | 1 ms | 332 KB | Output is correct |
60 | Correct | 1 ms | 332 KB | Output is correct |
61 | Correct | 1 ms | 332 KB | Output is correct |
62 | Correct | 1 ms | 332 KB | Output is correct |
63 | Correct | 1 ms | 332 KB | Output is correct |
64 | Correct | 1 ms | 332 KB | Output is correct |
65 | Correct | 1 ms | 332 KB | Output is correct |
66 | Correct | 1 ms | 332 KB | Output is correct |
67 | Correct | 1 ms | 336 KB | Output is correct |
68 | Correct | 1 ms | 332 KB | Output is correct |
69 | Correct | 1 ms | 344 KB | Output is correct |
70 | Correct | 1 ms | 332 KB | Output is correct |
71 | Correct | 1 ms | 336 KB | Output is correct |
72 | Correct | 1 ms | 332 KB | Output is correct |
73 | Correct | 1 ms | 332 KB | Output is correct |
74 | Correct | 6 ms | 1100 KB | Output is correct |
75 | Correct | 4 ms | 1100 KB | Output is correct |
76 | Correct | 4 ms | 1100 KB | Output is correct |
77 | Correct | 4 ms | 1100 KB | Output is correct |
78 | Correct | 4 ms | 1100 KB | Output is correct |
79 | Correct | 4 ms | 1140 KB | Output is correct |
80 | Correct | 4 ms | 1100 KB | Output is correct |
81 | Correct | 6 ms | 1360 KB | Output is correct |
82 | Correct | 6 ms | 1356 KB | Output is correct |
83 | Correct | 6 ms | 1384 KB | Output is correct |
84 | Correct | 4 ms | 1100 KB | Output is correct |
85 | Correct | 6 ms | 1356 KB | Output is correct |
86 | Correct | 6 ms | 1356 KB | Output is correct |
87 | Correct | 6 ms | 1288 KB | Output is correct |
88 | Correct | 4 ms | 1100 KB | Output is correct |
89 | Correct | 5 ms | 1228 KB | Output is correct |
90 | Correct | 5 ms | 1228 KB | Output is correct |
91 | Correct | 5 ms | 1228 KB | Output is correct |
92 | Correct | 4 ms | 1100 KB | Output is correct |
93 | Correct | 6 ms | 1100 KB | Output is correct |
94 | Correct | 4 ms | 1100 KB | Output is correct |
95 | Correct | 4 ms | 1100 KB | Output is correct |
96 | Correct | 4 ms | 1104 KB | Output is correct |
97 | Correct | 4 ms | 1100 KB | Output is correct |
98 | Correct | 4 ms | 1100 KB | Output is correct |
99 | Correct | 4 ms | 1100 KB | Output is correct |
100 | Correct | 4 ms | 1100 KB | Output is correct |
101 | Correct | 6 ms | 1484 KB | Output is correct |
102 | Correct | 5 ms | 1404 KB | Output is correct |
103 | Correct | 5 ms | 1356 KB | Output is correct |
104 | Correct | 5 ms | 1356 KB | Output is correct |
105 | Correct | 5 ms | 1356 KB | Output is correct |
106 | Correct | 5 ms | 1356 KB | Output is correct |
107 | Correct | 5 ms | 1360 KB | Output is correct |
108 | Correct | 5 ms | 1356 KB | Output is correct |
109 | Correct | 5 ms | 1356 KB | Output is correct |
110 | Correct | 3 ms | 1104 KB | Output is correct |
111 | Correct | 248 ms | 27980 KB | Output is correct |
112 | Correct | 266 ms | 28028 KB | Output is correct |
113 | Correct | 255 ms | 27968 KB | Output is correct |
114 | Correct | 275 ms | 27728 KB | Output is correct |
115 | Correct | 251 ms | 27512 KB | Output is correct |
116 | Correct | 234 ms | 27260 KB | Output is correct |
117 | Correct | 244 ms | 27264 KB | Output is correct |
118 | Correct | 355 ms | 37316 KB | Output is correct |
119 | Correct | 361 ms | 36456 KB | Output is correct |
120 | Correct | 294 ms | 32688 KB | Output is correct |
121 | Correct | 209 ms | 27332 KB | Output is correct |
122 | Correct | 326 ms | 33820 KB | Output is correct |
123 | Correct | 294 ms | 33192 KB | Output is correct |
124 | Correct | 299 ms | 32536 KB | Output is correct |
125 | Correct | 231 ms | 27248 KB | Output is correct |
126 | Correct | 254 ms | 29256 KB | Output is correct |
127 | Correct | 242 ms | 29124 KB | Output is correct |
128 | Correct | 275 ms | 28992 KB | Output is correct |
129 | Correct | 228 ms | 27256 KB | Output is correct |
130 | Correct | 273 ms | 28228 KB | Output is correct |
131 | Correct | 239 ms | 28228 KB | Output is correct |
132 | Correct | 235 ms | 28132 KB | Output is correct |
133 | Correct | 259 ms | 27204 KB | Output is correct |
134 | Correct | 252 ms | 28020 KB | Output is correct |
135 | Correct | 252 ms | 27972 KB | Output is correct |
136 | Correct | 241 ms | 27980 KB | Output is correct |
137 | Correct | 239 ms | 27324 KB | Output is correct |
138 | Correct | 234 ms | 27472 KB | Output is correct |
139 | Correct | 246 ms | 27500 KB | Output is correct |
140 | Correct | 247 ms | 27560 KB | Output is correct |
141 | Correct | 228 ms | 27204 KB | Output is correct |
142 | Correct | 197 ms | 38028 KB | Output is correct |
143 | Correct | 200 ms | 38120 KB | Output is correct |
144 | Correct | 192 ms | 37936 KB | Output is correct |
145 | Correct | 162 ms | 37788 KB | Output is correct |
146 | Correct | 165 ms | 37616 KB | Output is correct |
147 | Correct | 156 ms | 37396 KB | Output is correct |
148 | Correct | 195 ms | 37156 KB | Output is correct |
149 | Correct | 193 ms | 37028 KB | Output is correct |
150 | Correct | 155 ms | 36792 KB | Output is correct |
151 | Correct | 151 ms | 35652 KB | Output is correct |
152 | Correct | 95 ms | 27204 KB | Output is correct |
153 | Correct | 166 ms | 37848 KB | Output is correct |
154 | Correct | 164 ms | 37636 KB | Output is correct |
155 | Correct | 156 ms | 37444 KB | Output is correct |
156 | Correct | 159 ms | 37364 KB | Output is correct |
157 | Correct | 165 ms | 37108 KB | Output is correct |
158 | Correct | 159 ms | 36872 KB | Output is correct |
159 | Correct | 179 ms | 35864 KB | Output is correct |
160 | Correct | 88 ms | 27168 KB | Output is correct |
161 | Correct | 289 ms | 32956 KB | Output is correct |
162 | Correct | 313 ms | 32800 KB | Output is correct |
163 | Correct | 312 ms | 32620 KB | Output is correct |
164 | Correct | 347 ms | 32436 KB | Output is correct |
165 | Correct | 335 ms | 32200 KB | Output is correct |
166 | Correct | 95 ms | 27164 KB | Output is correct |
167 | Correct | 142 ms | 32764 KB | Output is correct |
168 | Correct | 142 ms | 32524 KB | Output is correct |
169 | Correct | 140 ms | 32324 KB | Output is correct |
170 | Correct | 154 ms | 32068 KB | Output is correct |
171 | Correct | 137 ms | 26180 KB | Output is correct |
172 | Correct | 147 ms | 26804 KB | Output is correct |
173 | Correct | 337 ms | 33076 KB | Output is correct |
174 | Correct | 315 ms | 32996 KB | Output is correct |
175 | Correct | 314 ms | 32940 KB | Output is correct |
176 | Correct | 286 ms | 31916 KB | Output is correct |