#include <bits/stdc++.h>
using namespace std;
struct node {
int mn, mx, lazymn, lazymx;
bool hv;
};
vector<node> tr[20];
vector<pair<int, int>> B;
void build(int lay, int p, int l, int r) {
if (l == r) {
tr[lay][p].mn = B[l].first;
tr[lay][p].mx = B[l].second;
tr[lay][p].lazymn = tr[lay][p].lazymx = -1;
tr[lay][p].hv = false;
return;
}
tr[lay][p].hv = true;
int mid = (l + r) / 2;
build(lay, p * 2, l, mid);
build(lay, p * 2 + 1, mid + 1, r);
tr[lay][p].mn = min(tr[lay][p * 2].mn, tr[lay][p * 2 + 1].mn);
tr[lay][p].mx = max(tr[lay][p * 2].mx, tr[lay][p * 2 + 1].mx);
tr[lay][p].lazymn = tr[lay][p].lazymx = -1;
return;
}
void push(int lay, int p) {
if (tr[lay][p].lazymn != -1) {
int me = tr[lay][p].lazymn;
if (tr[lay][p].hv) {
if (tr[lay][p * 2].lazymn == -1) tr[lay][p * 2].lazymn = me;
else tr[lay][p * 2].lazymn = min(tr[lay][p * 2].lazymn, me);
tr[lay][p * 2].mn = min(tr[lay][p * 2].mn, me);
if (tr[lay][p * 2 + 1].lazymn == -1) tr[lay][p * 2 + 1].lazymn = me;
else tr[lay][p * 2 + 1].lazymn = min(tr[lay][p * 2 + 1].lazymn, me);
tr[lay][p * 2 + 1].mn = min(tr[lay][p * 2 + 1].mn, me);
}
tr[lay][p].lazymn = -1;
}
if (tr[lay][p].lazymx != -1) {
int me = tr[lay][p].lazymx;
if (tr[lay][p].hv) {
if (tr[lay][p * 2].lazymx == -1) tr[lay][p * 2].lazymx = me;
else tr[lay][p * 2].lazymx = max(tr[lay][p * 2].lazymx, me);
tr[lay][p * 2].mx = max(tr[lay][p * 2].mx, me);
if (tr[lay][p * 2 + 1].lazymx == -1) tr[lay][p * 2 + 1].lazymx = me;
else tr[lay][p * 2 + 1].lazymx = max(tr[lay][p * 2 + 1].lazymx, me);
tr[lay][p * 2 + 1].mx = max(tr[lay][p * 2 + 1].mx, me);
}
tr[lay][p].lazymx = -1;
}
return;
}
void up(int lay, int p, int l, int r, int x, int y, int num, int mode) {
if (x > r || y < l) return;
push(lay, p);
if (x <= l && y >= r) {
if (mode == -1) {
tr[lay][p].lazymn = num;
tr[lay][p].mn = min(tr[lay][p].mn, num);
}
else {
tr[lay][p].lazymx = num;
tr[lay][p].mx = max(tr[lay][p].mx, num);
}
return;
}
int mid = (l + r) / 2;
up(lay, p * 2, l, mid, x, y, num, mode);
up(lay, p * 2 + 1, mid + 1, r, x, y, num, mode);
tr[lay][p].mn = min(tr[lay][p * 2].mn, tr[lay][p * 2 + 1].mn);
tr[lay][p].mx = max(tr[lay][p * 2].mx, tr[lay][p * 2 + 1].mx);
return;
}
pair<int, int> qu(int lay, int p, int l, int r, int x, int y) {
if (x > r || y < l) return {1e9, -1};
push(lay, p);
if (x <= l && y >= r) {
return {tr[lay][p].mn, tr[lay][p].mx};
}
int mid = (l + r) / 2;
auto pr1 = qu(lay, p * 2, l, mid, x, y);
auto pr2 = qu(lay, p * 2 + 1, mid + 1, r, x, y);
pair<int, int> ans;
ans.first = min(pr1.first, pr2.first);
ans.second = max(pr1.second, pr2.second);
return ans;
}
int main() {
ios::sync_with_stdio(false);
int n, m, k, q, r1, r2;
cin >> n >> k >> m;
vector<pair<int, int>> A(m + 1);
for (int i = 1; i <= m; i++) {
cin >> r1 >> r2;
A[i] = {r1, r2};
}
cin >> q;
vector<pair<int, int>> Q(q + 1);
for (int i = 1; i <= q; i++) {
cin >> r1 >> r2;
Q[i] = {r1, r2};
}
int two = 1, ct = 1;
while (ct < n) {
ct *= 2;
two++;
}
for (int i = 0; i <= two; i++) {
tr[i].reserve(4 * n + 1);
}
B.reserve(n + 1);
for (int i = 1; i <= n; i++) {
B[i] = {i, i};
}
build(0, 1, 1, n);
for (int i = 1; i <= m; i++) {
int sl, sr;
if (A[i].first < A[i].second) {
sl = A[i].first;
sr = A[i].first + k - 1;
up(0, 1, 1, n, sl, sr, A[i].second, 1);
}
else {
sl = A[i].first - k + 1;
sr = A[i].first;
up(0, 1, 1, n, sl, sr, A[i].second, -1);
}
}
for (int i = 1; i <= two; i++) {
int last = i - 1;
for (int j = 1; j <= n; j++) {
int l, r;
auto pr = qu(last, 1, 1, n, j, j);
l = pr.first;
r = pr.second;
pr = qu(last, 1, 1, n, l, r);
B[j] = pr;
}
build(i, 1, 1, n);
}
for (int i = 1; i <= q; i++) {
int ans = 0;
int l, r;
l = r = Q[i].first;
auto pr = qu(two, 1, 1, n, l, r);
if (Q[i].second < pr.first || Q[i].second > pr.second) {
ans = -1;
}
else {
for (int j = two - 1; j >= 0; j--) {
pr = qu(j, 1, 1, n, l, r);
if (Q[i].second < pr.first || Q[i].second > pr.second) {
ans += (1 << j);
l = pr.first;
r = pr.second;
}
}
ans++;
}
cout << ans << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
14 ms |
1320 KB |
Output is correct |
14 |
Correct |
19 ms |
1364 KB |
Output is correct |
15 |
Correct |
9 ms |
1364 KB |
Output is correct |
16 |
Correct |
8 ms |
1300 KB |
Output is correct |
17 |
Correct |
19 ms |
1296 KB |
Output is correct |
18 |
Correct |
9 ms |
1312 KB |
Output is correct |
19 |
Correct |
12 ms |
1408 KB |
Output is correct |
20 |
Correct |
11 ms |
1364 KB |
Output is correct |
21 |
Correct |
5 ms |
1364 KB |
Output is correct |
22 |
Correct |
12 ms |
1324 KB |
Output is correct |
23 |
Correct |
13 ms |
1364 KB |
Output is correct |
24 |
Correct |
13 ms |
1336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
947 ms |
99256 KB |
Output is correct |
2 |
Correct |
940 ms |
99224 KB |
Output is correct |
3 |
Correct |
972 ms |
99560 KB |
Output is correct |
4 |
Correct |
887 ms |
99388 KB |
Output is correct |
5 |
Correct |
671 ms |
100256 KB |
Output is correct |
6 |
Correct |
918 ms |
100432 KB |
Output is correct |
7 |
Correct |
576 ms |
100104 KB |
Output is correct |
8 |
Correct |
532 ms |
99488 KB |
Output is correct |
9 |
Correct |
490 ms |
99464 KB |
Output is correct |
10 |
Correct |
973 ms |
100432 KB |
Output is correct |
11 |
Correct |
933 ms |
100172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1156 ms |
99872 KB |
Output is correct |
2 |
Correct |
927 ms |
100788 KB |
Output is correct |
3 |
Correct |
1419 ms |
100276 KB |
Output is correct |
4 |
Correct |
789 ms |
100732 KB |
Output is correct |
5 |
Correct |
757 ms |
100700 KB |
Output is correct |
6 |
Correct |
748 ms |
100680 KB |
Output is correct |
7 |
Correct |
1381 ms |
100748 KB |
Output is correct |
8 |
Correct |
1217 ms |
100884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
951 ms |
100708 KB |
Output is correct |
2 |
Correct |
1432 ms |
100196 KB |
Output is correct |
3 |
Correct |
1364 ms |
99748 KB |
Output is correct |
4 |
Correct |
1361 ms |
99544 KB |
Output is correct |
5 |
Correct |
1123 ms |
99276 KB |
Output is correct |
6 |
Correct |
1275 ms |
99288 KB |
Output is correct |
7 |
Correct |
1010 ms |
99924 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
11 ms |
1428 KB |
Output is correct |
10 |
Correct |
1002 ms |
100304 KB |
Output is correct |
11 |
Correct |
1026 ms |
100756 KB |
Output is correct |
12 |
Correct |
1140 ms |
100656 KB |
Output is correct |
13 |
Correct |
1092 ms |
100772 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
16 ms |
1404 KB |
Output is correct |
16 |
Correct |
986 ms |
100180 KB |
Output is correct |
17 |
Correct |
1443 ms |
101024 KB |
Output is correct |
18 |
Correct |
1354 ms |
101088 KB |
Output is correct |
19 |
Correct |
1306 ms |
100840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
14 ms |
1320 KB |
Output is correct |
14 |
Correct |
19 ms |
1364 KB |
Output is correct |
15 |
Correct |
9 ms |
1364 KB |
Output is correct |
16 |
Correct |
8 ms |
1300 KB |
Output is correct |
17 |
Correct |
19 ms |
1296 KB |
Output is correct |
18 |
Correct |
9 ms |
1312 KB |
Output is correct |
19 |
Correct |
12 ms |
1408 KB |
Output is correct |
20 |
Correct |
11 ms |
1364 KB |
Output is correct |
21 |
Correct |
5 ms |
1364 KB |
Output is correct |
22 |
Correct |
12 ms |
1324 KB |
Output is correct |
23 |
Correct |
13 ms |
1364 KB |
Output is correct |
24 |
Correct |
13 ms |
1336 KB |
Output is correct |
25 |
Correct |
947 ms |
99256 KB |
Output is correct |
26 |
Correct |
940 ms |
99224 KB |
Output is correct |
27 |
Correct |
972 ms |
99560 KB |
Output is correct |
28 |
Correct |
887 ms |
99388 KB |
Output is correct |
29 |
Correct |
671 ms |
100256 KB |
Output is correct |
30 |
Correct |
918 ms |
100432 KB |
Output is correct |
31 |
Correct |
576 ms |
100104 KB |
Output is correct |
32 |
Correct |
532 ms |
99488 KB |
Output is correct |
33 |
Correct |
490 ms |
99464 KB |
Output is correct |
34 |
Correct |
973 ms |
100432 KB |
Output is correct |
35 |
Correct |
933 ms |
100172 KB |
Output is correct |
36 |
Correct |
1156 ms |
99872 KB |
Output is correct |
37 |
Correct |
927 ms |
100788 KB |
Output is correct |
38 |
Correct |
1419 ms |
100276 KB |
Output is correct |
39 |
Correct |
789 ms |
100732 KB |
Output is correct |
40 |
Correct |
757 ms |
100700 KB |
Output is correct |
41 |
Correct |
748 ms |
100680 KB |
Output is correct |
42 |
Correct |
1381 ms |
100748 KB |
Output is correct |
43 |
Correct |
1217 ms |
100884 KB |
Output is correct |
44 |
Correct |
951 ms |
100708 KB |
Output is correct |
45 |
Correct |
1432 ms |
100196 KB |
Output is correct |
46 |
Correct |
1364 ms |
99748 KB |
Output is correct |
47 |
Correct |
1361 ms |
99544 KB |
Output is correct |
48 |
Correct |
1123 ms |
99276 KB |
Output is correct |
49 |
Correct |
1275 ms |
99288 KB |
Output is correct |
50 |
Correct |
1010 ms |
99924 KB |
Output is correct |
51 |
Correct |
2 ms |
468 KB |
Output is correct |
52 |
Correct |
11 ms |
1428 KB |
Output is correct |
53 |
Correct |
1002 ms |
100304 KB |
Output is correct |
54 |
Correct |
1026 ms |
100756 KB |
Output is correct |
55 |
Correct |
1140 ms |
100656 KB |
Output is correct |
56 |
Correct |
1092 ms |
100772 KB |
Output is correct |
57 |
Correct |
2 ms |
468 KB |
Output is correct |
58 |
Correct |
16 ms |
1404 KB |
Output is correct |
59 |
Correct |
986 ms |
100180 KB |
Output is correct |
60 |
Correct |
1443 ms |
101024 KB |
Output is correct |
61 |
Correct |
1354 ms |
101088 KB |
Output is correct |
62 |
Correct |
1306 ms |
100840 KB |
Output is correct |
63 |
Correct |
1242 ms |
100088 KB |
Output is correct |
64 |
Correct |
1432 ms |
100076 KB |
Output is correct |
65 |
Correct |
1273 ms |
101380 KB |
Output is correct |
66 |
Correct |
641 ms |
103624 KB |
Output is correct |
67 |
Correct |
1264 ms |
103860 KB |
Output is correct |
68 |
Correct |
1236 ms |
103524 KB |
Output is correct |
69 |
Correct |
891 ms |
103448 KB |
Output is correct |
70 |
Correct |
1183 ms |
103536 KB |
Output is correct |
71 |
Correct |
1520 ms |
103684 KB |
Output is correct |