#include <bits/stdc++.h>
using namespace std;
const int $L = 20;
int main() {
int N, K, M;
cin >> N >> K >> M;
array<vector<int>, $L> lb, rb;
lb.fill(vector<int>(2 * N, -1));
rb.fill(vector<int>(2 * N, -1));
vector<int> A(M), B(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i];
A[i]--, B[i]--;
}
multiset<int> mse;
vector<vector<int>> ins(N), era(N);
for (int i = 0; i < M; i++) {
if (A[i] > B[i]) {
ins[A[i]].push_back(B[i]);
era[max(A[i] - K + 1, B[i] + 1)].push_back(B[i]);
}
}
for (int i = N - 1; i >= 0; i--) {
for (int k : ins[i])
mse.insert(k);
ins[i].clear();
lb[0][i + N] = min(i, mse.empty() ? N : *mse.begin());
for (int k : era[i])
mse.erase(mse.lower_bound(k));
era[i].clear();
}
assert(mse.empty());
for (int i = 0; i < M; i++) {
if (A[i] < B[i]) {
ins[A[i]].push_back(B[i]);
era[min(A[i] + K - 1, B[i] - 1)].push_back(B[i]);
}
}
for (int i = 0; i < N; i++) {
for (int k : ins[i])
mse.insert(k);
ins[i].clear();
rb[0][i + N] = max(i, mse.empty() ? 0 : *mse.rbegin());
for (int k : era[i])
mse.erase(mse.lower_bound(k));
era[i].clear();
}
assert(mse.empty());
for (int b = 1; b < $L; b++) {
for (int i = N - 1; i >= 1; i--) {
lb[b - 1][i] = min(lb[b - 1][i * 2], lb[b - 1][i * 2 + 1]);
rb[b - 1][i] = max(rb[b - 1][i * 2], rb[b - 1][i * 2 + 1]);
}
for (int i = 0; i < N; i++) {
int l = lb[b - 1][i + N], r = rb[b - 1][i + N];
int retl = N, retr = 0;
for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
retl = min(retl, lb[b - 1][l]);
retr = max(retr, rb[b - 1][l]);
l++;
}
if (r & 1) {
r--;
retl = min(retl, lb[b - 1][r]);
retr = max(retr, rb[b - 1][r]);
}
}
lb[b][i + N] = retl, rb[b][i + N] = retr;
}
}
int Q;
cin >> Q;
while (Q--) {
int u, v;
cin >> u >> v;
u--, v--;
int l = u, r = u;
if (v < lb[$L - 1][u + N] || rb[$L - 1][u + N] < v) {
cout << -1 << '\n';
} else {
int ans = 0;
for (int b = $L - 1; b >= 0; b--) {
int retl = N, retr = 0;
for (int ll = l + N, rr = r + N + 1; ll < rr; ll >>= 1, rr >>= 1) {
if (ll & 1) {
retl = min(retl, lb[b][ll]);
retr = max(retr, rb[b][ll]);
ll++;
}
if (rr & 1) {
rr--;
retl = min(retl, lb[b][rr]);
retr = max(retr, rb[b][rr]);
}
}
if (v < retl || retr < v) {
l = retl, r = retr;
ans |= (1 << b);
}
}
cout << ans + 1 << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
432 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
432 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
8 ms |
1096 KB |
Output is correct |
14 |
Correct |
11 ms |
1128 KB |
Output is correct |
15 |
Correct |
3 ms |
1084 KB |
Output is correct |
16 |
Correct |
7 ms |
1108 KB |
Output is correct |
17 |
Correct |
8 ms |
1064 KB |
Output is correct |
18 |
Correct |
6 ms |
1108 KB |
Output is correct |
19 |
Correct |
8 ms |
1124 KB |
Output is correct |
20 |
Correct |
7 ms |
1108 KB |
Output is correct |
21 |
Correct |
3 ms |
1108 KB |
Output is correct |
22 |
Correct |
7 ms |
1080 KB |
Output is correct |
23 |
Correct |
7 ms |
1112 KB |
Output is correct |
24 |
Correct |
6 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
42088 KB |
Output is correct |
2 |
Correct |
191 ms |
42864 KB |
Output is correct |
3 |
Correct |
255 ms |
44168 KB |
Output is correct |
4 |
Correct |
191 ms |
42404 KB |
Output is correct |
5 |
Correct |
342 ms |
46780 KB |
Output is correct |
6 |
Correct |
227 ms |
46512 KB |
Output is correct |
7 |
Correct |
238 ms |
48564 KB |
Output is correct |
8 |
Correct |
171 ms |
42852 KB |
Output is correct |
9 |
Correct |
202 ms |
43416 KB |
Output is correct |
10 |
Correct |
272 ms |
45756 KB |
Output is correct |
11 |
Correct |
275 ms |
45644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
312 ms |
43412 KB |
Output is correct |
2 |
Correct |
391 ms |
47500 KB |
Output is correct |
3 |
Correct |
371 ms |
45296 KB |
Output is correct |
4 |
Correct |
332 ms |
49208 KB |
Output is correct |
5 |
Correct |
410 ms |
48248 KB |
Output is correct |
6 |
Correct |
363 ms |
48596 KB |
Output is correct |
7 |
Correct |
380 ms |
46264 KB |
Output is correct |
8 |
Correct |
411 ms |
46452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
439 ms |
45460 KB |
Output is correct |
2 |
Correct |
421 ms |
43816 KB |
Output is correct |
3 |
Correct |
375 ms |
41268 KB |
Output is correct |
4 |
Correct |
327 ms |
38848 KB |
Output is correct |
5 |
Correct |
241 ms |
37892 KB |
Output is correct |
6 |
Correct |
263 ms |
37820 KB |
Output is correct |
7 |
Correct |
320 ms |
47148 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
8 ms |
1080 KB |
Output is correct |
10 |
Correct |
364 ms |
48596 KB |
Output is correct |
11 |
Correct |
459 ms |
50504 KB |
Output is correct |
12 |
Correct |
459 ms |
48440 KB |
Output is correct |
13 |
Correct |
463 ms |
50408 KB |
Output is correct |
14 |
Correct |
1 ms |
428 KB |
Output is correct |
15 |
Correct |
9 ms |
1108 KB |
Output is correct |
16 |
Correct |
282 ms |
45932 KB |
Output is correct |
17 |
Correct |
509 ms |
46652 KB |
Output is correct |
18 |
Correct |
555 ms |
46528 KB |
Output is correct |
19 |
Correct |
467 ms |
46528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
432 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
8 ms |
1096 KB |
Output is correct |
14 |
Correct |
11 ms |
1128 KB |
Output is correct |
15 |
Correct |
3 ms |
1084 KB |
Output is correct |
16 |
Correct |
7 ms |
1108 KB |
Output is correct |
17 |
Correct |
8 ms |
1064 KB |
Output is correct |
18 |
Correct |
6 ms |
1108 KB |
Output is correct |
19 |
Correct |
8 ms |
1124 KB |
Output is correct |
20 |
Correct |
7 ms |
1108 KB |
Output is correct |
21 |
Correct |
3 ms |
1108 KB |
Output is correct |
22 |
Correct |
7 ms |
1080 KB |
Output is correct |
23 |
Correct |
7 ms |
1112 KB |
Output is correct |
24 |
Correct |
6 ms |
1108 KB |
Output is correct |
25 |
Correct |
186 ms |
42088 KB |
Output is correct |
26 |
Correct |
191 ms |
42864 KB |
Output is correct |
27 |
Correct |
255 ms |
44168 KB |
Output is correct |
28 |
Correct |
191 ms |
42404 KB |
Output is correct |
29 |
Correct |
342 ms |
46780 KB |
Output is correct |
30 |
Correct |
227 ms |
46512 KB |
Output is correct |
31 |
Correct |
238 ms |
48564 KB |
Output is correct |
32 |
Correct |
171 ms |
42852 KB |
Output is correct |
33 |
Correct |
202 ms |
43416 KB |
Output is correct |
34 |
Correct |
272 ms |
45756 KB |
Output is correct |
35 |
Correct |
275 ms |
45644 KB |
Output is correct |
36 |
Correct |
312 ms |
43412 KB |
Output is correct |
37 |
Correct |
391 ms |
47500 KB |
Output is correct |
38 |
Correct |
371 ms |
45296 KB |
Output is correct |
39 |
Correct |
332 ms |
49208 KB |
Output is correct |
40 |
Correct |
410 ms |
48248 KB |
Output is correct |
41 |
Correct |
363 ms |
48596 KB |
Output is correct |
42 |
Correct |
380 ms |
46264 KB |
Output is correct |
43 |
Correct |
411 ms |
46452 KB |
Output is correct |
44 |
Correct |
439 ms |
45460 KB |
Output is correct |
45 |
Correct |
421 ms |
43816 KB |
Output is correct |
46 |
Correct |
375 ms |
41268 KB |
Output is correct |
47 |
Correct |
327 ms |
38848 KB |
Output is correct |
48 |
Correct |
241 ms |
37892 KB |
Output is correct |
49 |
Correct |
263 ms |
37820 KB |
Output is correct |
50 |
Correct |
320 ms |
47148 KB |
Output is correct |
51 |
Correct |
1 ms |
340 KB |
Output is correct |
52 |
Correct |
8 ms |
1080 KB |
Output is correct |
53 |
Correct |
364 ms |
48596 KB |
Output is correct |
54 |
Correct |
459 ms |
50504 KB |
Output is correct |
55 |
Correct |
459 ms |
48440 KB |
Output is correct |
56 |
Correct |
463 ms |
50408 KB |
Output is correct |
57 |
Correct |
1 ms |
428 KB |
Output is correct |
58 |
Correct |
9 ms |
1108 KB |
Output is correct |
59 |
Correct |
282 ms |
45932 KB |
Output is correct |
60 |
Correct |
509 ms |
46652 KB |
Output is correct |
61 |
Correct |
555 ms |
46528 KB |
Output is correct |
62 |
Correct |
467 ms |
46528 KB |
Output is correct |
63 |
Correct |
367 ms |
43056 KB |
Output is correct |
64 |
Correct |
449 ms |
44492 KB |
Output is correct |
65 |
Correct |
388 ms |
43244 KB |
Output is correct |
66 |
Correct |
373 ms |
47548 KB |
Output is correct |
67 |
Correct |
434 ms |
47352 KB |
Output is correct |
68 |
Correct |
419 ms |
46376 KB |
Output is correct |
69 |
Correct |
366 ms |
48508 KB |
Output is correct |
70 |
Correct |
378 ms |
46396 KB |
Output is correct |
71 |
Correct |
460 ms |
46376 KB |
Output is correct |