#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
using namespace std;
struct Range {
int l, r;
Range(int x, int y) {
l = x;
r = y;
}
Range(int x) { l = r = x; }
Range() {
l = INT_MAX;
r = INT_MIN;
}
Range operator|(Range a) { return Range(min(l, a.l), max(r, a.r)); }
void operator|=(Range a) {
l = min(l, a.l);
r = max(r, a.r);
}
};
struct Segtree {
vector<Range> v;
int c;
void update(int x, Range y) {
x += 1 << c;
while (x) {
v[x] |= y;
x /= 2;
}
}
Range calc(int x) { return v[x + (1 << c)]; }
Range calc(int l, int r) {
l += 1 << c;
r += 1 << c;
Range x;
while (l <= r) {
x |= v[l];
x |= v[r];
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return x;
}
Range calc(Range x) { return calc(x.l, x.r); }
Segtree() {}
Segtree(int n) {
c = 0;
while ((1 << c) < n) c++;
v.resize(1 << c + 1);
}
};
int N, K, M, Q, A[200000], B[200000], S[50000], T[50000];
Range R[100000];
Segtree Seg[18];
int query(int s, int t) {
int cnt = 0;
Range p;
p = Range(s);
for (int i = 17; i >= 0; i--) {
Range q = Seg[i].calc(p);
if (!(q.l <= t && t <= q.r)) {
p = q;
cnt += 1 << i;
}
}
if (cnt == (1 << 18) - 1)
return -1;
else
return cnt + 1;
}
int main() {
cin >> N >> K >> M;
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i];
A[i]--;
B[i]--;
}
cin >> Q;
for (int i = 0; i < Q; i++) {
cin >> S[i] >> T[i];
S[i]--;
T[i]--;
}
for (int i = 0; i < 18; i++) {
Seg[i] = Segtree(N);
}
for (int i = 0; i < N; i++) {
R[i] = Range(i);
}
for (int i = 0; i < M; i++) {
R[A[i]] |= Range(B[i]);
}
deque<pair<int, int>> q;
for (int i = 0; i < N; i++) {
while (!q.empty() && q.back().first < R[i].r) q.pop_back();
q.push_back({R[i].r, i + K - 1});
Seg[0].update(i, Range(q.front().first));
while (!q.empty() && q.front().second <= i) q.pop_front();
}
q.clear();
for (int i = N - 1; i >= 0; i--) {
while (!q.empty() && q.back().first > R[i].l) q.pop_back();
q.push_back({R[i].l, i - K + 1});
Seg[0].update(i, Range(q.front().first));
while (!q.empty() && q.front().second >= i) q.pop_front();
}
for (int i = 0; i < 17; i++) {
for (int j = 0; j < N; j++) {
Seg[i + 1].update(j, Seg[i].calc(Seg[i].calc(j)));
}
}
for (int i = 0; i < Q; i++) {
cout << query(S[i], T[i]) << endl;
}
}
Compilation message
Main.cpp: In constructor 'Segtree::Segtree(int)':
Main.cpp:53:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
53 | v.resize(1 << c + 1);
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1228 KB |
Output is correct |
2 |
Correct |
2 ms |
1228 KB |
Output is correct |
3 |
Correct |
1 ms |
1228 KB |
Output is correct |
4 |
Correct |
2 ms |
1228 KB |
Output is correct |
5 |
Correct |
2 ms |
1228 KB |
Output is correct |
6 |
Correct |
2 ms |
1228 KB |
Output is correct |
7 |
Correct |
2 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
1228 KB |
Output is correct |
9 |
Correct |
2 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
972 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1228 KB |
Output is correct |
2 |
Correct |
2 ms |
1228 KB |
Output is correct |
3 |
Correct |
1 ms |
1228 KB |
Output is correct |
4 |
Correct |
2 ms |
1228 KB |
Output is correct |
5 |
Correct |
2 ms |
1228 KB |
Output is correct |
6 |
Correct |
2 ms |
1228 KB |
Output is correct |
7 |
Correct |
2 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
1228 KB |
Output is correct |
9 |
Correct |
2 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
972 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1228 KB |
Output is correct |
13 |
Correct |
8 ms |
1612 KB |
Output is correct |
14 |
Correct |
7 ms |
1612 KB |
Output is correct |
15 |
Correct |
3 ms |
1612 KB |
Output is correct |
16 |
Correct |
12 ms |
1704 KB |
Output is correct |
17 |
Correct |
7 ms |
1612 KB |
Output is correct |
18 |
Correct |
7 ms |
1612 KB |
Output is correct |
19 |
Correct |
7 ms |
1612 KB |
Output is correct |
20 |
Correct |
7 ms |
1612 KB |
Output is correct |
21 |
Correct |
4 ms |
1612 KB |
Output is correct |
22 |
Correct |
7 ms |
1612 KB |
Output is correct |
23 |
Correct |
8 ms |
1612 KB |
Output is correct |
24 |
Correct |
7 ms |
1740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
219 ms |
38736 KB |
Output is correct |
2 |
Correct |
191 ms |
38628 KB |
Output is correct |
3 |
Correct |
205 ms |
38752 KB |
Output is correct |
4 |
Correct |
183 ms |
38724 KB |
Output is correct |
5 |
Correct |
299 ms |
39648 KB |
Output is correct |
6 |
Correct |
242 ms |
39648 KB |
Output is correct |
7 |
Correct |
289 ms |
40580 KB |
Output is correct |
8 |
Correct |
244 ms |
38876 KB |
Output is correct |
9 |
Correct |
276 ms |
38876 KB |
Output is correct |
10 |
Correct |
280 ms |
39604 KB |
Output is correct |
11 |
Correct |
254 ms |
39628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
467 ms |
39464 KB |
Output is correct |
2 |
Correct |
439 ms |
40168 KB |
Output is correct |
3 |
Correct |
448 ms |
39556 KB |
Output is correct |
4 |
Correct |
420 ms |
40960 KB |
Output is correct |
5 |
Correct |
463 ms |
40064 KB |
Output is correct |
6 |
Correct |
417 ms |
40032 KB |
Output is correct |
7 |
Correct |
431 ms |
40216 KB |
Output is correct |
8 |
Correct |
509 ms |
40268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
585 ms |
40104 KB |
Output is correct |
2 |
Correct |
595 ms |
39544 KB |
Output is correct |
3 |
Correct |
425 ms |
39076 KB |
Output is correct |
4 |
Correct |
410 ms |
38872 KB |
Output is correct |
5 |
Correct |
334 ms |
38844 KB |
Output is correct |
6 |
Correct |
376 ms |
38580 KB |
Output is correct |
7 |
Correct |
349 ms |
40020 KB |
Output is correct |
8 |
Correct |
2 ms |
1228 KB |
Output is correct |
9 |
Correct |
10 ms |
1624 KB |
Output is correct |
10 |
Correct |
286 ms |
39652 KB |
Output is correct |
11 |
Correct |
367 ms |
40088 KB |
Output is correct |
12 |
Correct |
407 ms |
40036 KB |
Output is correct |
13 |
Correct |
525 ms |
40496 KB |
Output is correct |
14 |
Correct |
3 ms |
1228 KB |
Output is correct |
15 |
Correct |
9 ms |
1612 KB |
Output is correct |
16 |
Correct |
285 ms |
39648 KB |
Output is correct |
17 |
Correct |
655 ms |
40188 KB |
Output is correct |
18 |
Correct |
484 ms |
40196 KB |
Output is correct |
19 |
Correct |
505 ms |
40196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1228 KB |
Output is correct |
2 |
Correct |
2 ms |
1228 KB |
Output is correct |
3 |
Correct |
1 ms |
1228 KB |
Output is correct |
4 |
Correct |
2 ms |
1228 KB |
Output is correct |
5 |
Correct |
2 ms |
1228 KB |
Output is correct |
6 |
Correct |
2 ms |
1228 KB |
Output is correct |
7 |
Correct |
2 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
1228 KB |
Output is correct |
9 |
Correct |
2 ms |
1228 KB |
Output is correct |
10 |
Correct |
1 ms |
972 KB |
Output is correct |
11 |
Correct |
1 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1228 KB |
Output is correct |
13 |
Correct |
8 ms |
1612 KB |
Output is correct |
14 |
Correct |
7 ms |
1612 KB |
Output is correct |
15 |
Correct |
3 ms |
1612 KB |
Output is correct |
16 |
Correct |
12 ms |
1704 KB |
Output is correct |
17 |
Correct |
7 ms |
1612 KB |
Output is correct |
18 |
Correct |
7 ms |
1612 KB |
Output is correct |
19 |
Correct |
7 ms |
1612 KB |
Output is correct |
20 |
Correct |
7 ms |
1612 KB |
Output is correct |
21 |
Correct |
4 ms |
1612 KB |
Output is correct |
22 |
Correct |
7 ms |
1612 KB |
Output is correct |
23 |
Correct |
8 ms |
1612 KB |
Output is correct |
24 |
Correct |
7 ms |
1740 KB |
Output is correct |
25 |
Correct |
219 ms |
38736 KB |
Output is correct |
26 |
Correct |
191 ms |
38628 KB |
Output is correct |
27 |
Correct |
205 ms |
38752 KB |
Output is correct |
28 |
Correct |
183 ms |
38724 KB |
Output is correct |
29 |
Correct |
299 ms |
39648 KB |
Output is correct |
30 |
Correct |
242 ms |
39648 KB |
Output is correct |
31 |
Correct |
289 ms |
40580 KB |
Output is correct |
32 |
Correct |
244 ms |
38876 KB |
Output is correct |
33 |
Correct |
276 ms |
38876 KB |
Output is correct |
34 |
Correct |
280 ms |
39604 KB |
Output is correct |
35 |
Correct |
254 ms |
39628 KB |
Output is correct |
36 |
Correct |
467 ms |
39464 KB |
Output is correct |
37 |
Correct |
439 ms |
40168 KB |
Output is correct |
38 |
Correct |
448 ms |
39556 KB |
Output is correct |
39 |
Correct |
420 ms |
40960 KB |
Output is correct |
40 |
Correct |
463 ms |
40064 KB |
Output is correct |
41 |
Correct |
417 ms |
40032 KB |
Output is correct |
42 |
Correct |
431 ms |
40216 KB |
Output is correct |
43 |
Correct |
509 ms |
40268 KB |
Output is correct |
44 |
Correct |
585 ms |
40104 KB |
Output is correct |
45 |
Correct |
595 ms |
39544 KB |
Output is correct |
46 |
Correct |
425 ms |
39076 KB |
Output is correct |
47 |
Correct |
410 ms |
38872 KB |
Output is correct |
48 |
Correct |
334 ms |
38844 KB |
Output is correct |
49 |
Correct |
376 ms |
38580 KB |
Output is correct |
50 |
Correct |
349 ms |
40020 KB |
Output is correct |
51 |
Correct |
2 ms |
1228 KB |
Output is correct |
52 |
Correct |
10 ms |
1624 KB |
Output is correct |
53 |
Correct |
286 ms |
39652 KB |
Output is correct |
54 |
Correct |
367 ms |
40088 KB |
Output is correct |
55 |
Correct |
407 ms |
40036 KB |
Output is correct |
56 |
Correct |
525 ms |
40496 KB |
Output is correct |
57 |
Correct |
3 ms |
1228 KB |
Output is correct |
58 |
Correct |
9 ms |
1612 KB |
Output is correct |
59 |
Correct |
285 ms |
39648 KB |
Output is correct |
60 |
Correct |
655 ms |
40188 KB |
Output is correct |
61 |
Correct |
484 ms |
40196 KB |
Output is correct |
62 |
Correct |
505 ms |
40196 KB |
Output is correct |
63 |
Correct |
521 ms |
39184 KB |
Output is correct |
64 |
Correct |
541 ms |
39456 KB |
Output is correct |
65 |
Correct |
423 ms |
39252 KB |
Output is correct |
66 |
Correct |
569 ms |
40132 KB |
Output is correct |
67 |
Correct |
560 ms |
40316 KB |
Output is correct |
68 |
Correct |
425 ms |
40028 KB |
Output is correct |
69 |
Correct |
423 ms |
40112 KB |
Output is correct |
70 |
Correct |
518 ms |
40080 KB |
Output is correct |
71 |
Correct |
466 ms |
40228 KB |
Output is correct |