#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, K, m, q, mx[maxn], mn[maxn];
int f[18][maxn], g[18][maxn], st1[18][18][maxn], st2[18][18][maxn];
int main() {
scanf("%d %d %d", &n, &K, &m);
iota(mx + 1, mx + n + 1, 1);
iota(mn + 1, mn + n + 1, 1);
for (int i = 1, a, b; i <= m; i++) {
scanf("%d %d", &a, &b);
if (a < b) mx[a] = max(mx[a], b);
else mn[a] = min(mn[a], b);
}
deque<int> Q;
for (int i = n; i; i--) {
while (!Q.empty() && mn[Q.back()] > mn[i]) Q.pop_back();
Q.push_back(i);
while (Q.front() >= i + K) Q.pop_front();
f[0][i] = mn[Q.front()];
}
Q.clear();
for (int i = 1; i <= n; i++) {
while (!Q.empty() && mx[Q.back()] < mx[i]) Q.pop_back();
Q.push_back(i);
while (Q.front() <= i - K) Q.pop_front();
g[0][i] = mx[Q.front()];
}
auto qmin = [&](int st[18][maxn], int l, int r) {
int k = __lg(r - l + 1);
return min(st[k][l], st[k][r - (1 << k) + 1]);
};
auto qmax = [&](int st[18][maxn], int l, int r) {
int k = __lg(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
};
for (int k = 0; k < 18; k++) {
if (k) {
for (int i = 1; i <= n; i++) {
f[k][i] = qmin(st1[k - 1], f[k - 1][i], g[k - 1][i]);
g[k][i] = qmax(st2[k - 1], f[k - 1][i], g[k - 1][i]);
}
}
for (int i = 1; i <= n; i++) {
st1[k][0][i] = f[k][i], st2[k][0][i] = g[k][i];
}
for (int i = 1; i < 18; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
st1[k][i][j] = min(st1[k][i - 1][j], st1[k][i - 1][j + (1 << (i - 1))]);
st2[k][i][j] = max(st2[k][i - 1][j], st2[k][i - 1][j + (1 << (i - 1))]);
}
}
}
scanf("%d", &q);
while (q--) {
int s, t;
scanf("%d %d", &s, &t);
int l = s, r = s, ans = 0;
for (int i = 17; ~i; i--) {
int _l = qmin(st1[i], l, r), _r = qmax(st2[i], l, r);
if (_r < t || _l > t) l = _l, r = _r, ans |= 1 << i;
}
printf("%d\n", ans > n ? -1 : ans + 1);
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | scanf("%d %d %d", &n, &K, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
Main.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d", &s, &t);
| ~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2380 KB |
Output is correct |
2 |
Correct |
2 ms |
2380 KB |
Output is correct |
3 |
Correct |
2 ms |
2380 KB |
Output is correct |
4 |
Correct |
2 ms |
2380 KB |
Output is correct |
5 |
Correct |
2 ms |
2380 KB |
Output is correct |
6 |
Correct |
1 ms |
2380 KB |
Output is correct |
7 |
Correct |
2 ms |
2380 KB |
Output is correct |
8 |
Correct |
1 ms |
2380 KB |
Output is correct |
9 |
Correct |
2 ms |
2380 KB |
Output is correct |
10 |
Correct |
1 ms |
844 KB |
Output is correct |
11 |
Correct |
2 ms |
2380 KB |
Output is correct |
12 |
Correct |
1 ms |
2380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2380 KB |
Output is correct |
2 |
Correct |
2 ms |
2380 KB |
Output is correct |
3 |
Correct |
2 ms |
2380 KB |
Output is correct |
4 |
Correct |
2 ms |
2380 KB |
Output is correct |
5 |
Correct |
2 ms |
2380 KB |
Output is correct |
6 |
Correct |
1 ms |
2380 KB |
Output is correct |
7 |
Correct |
2 ms |
2380 KB |
Output is correct |
8 |
Correct |
1 ms |
2380 KB |
Output is correct |
9 |
Correct |
2 ms |
2380 KB |
Output is correct |
10 |
Correct |
1 ms |
844 KB |
Output is correct |
11 |
Correct |
2 ms |
2380 KB |
Output is correct |
12 |
Correct |
1 ms |
2380 KB |
Output is correct |
13 |
Correct |
5 ms |
5452 KB |
Output is correct |
14 |
Correct |
4 ms |
5452 KB |
Output is correct |
15 |
Correct |
4 ms |
5452 KB |
Output is correct |
16 |
Correct |
4 ms |
5452 KB |
Output is correct |
17 |
Correct |
4 ms |
5452 KB |
Output is correct |
18 |
Correct |
4 ms |
5452 KB |
Output is correct |
19 |
Correct |
4 ms |
5324 KB |
Output is correct |
20 |
Correct |
5 ms |
5452 KB |
Output is correct |
21 |
Correct |
4 ms |
5432 KB |
Output is correct |
22 |
Correct |
4 ms |
5452 KB |
Output is correct |
23 |
Correct |
4 ms |
5452 KB |
Output is correct |
24 |
Correct |
4 ms |
5452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
177 ms |
237372 KB |
Output is correct |
2 |
Correct |
148 ms |
237380 KB |
Output is correct |
3 |
Correct |
169 ms |
237400 KB |
Output is correct |
4 |
Correct |
161 ms |
237380 KB |
Output is correct |
5 |
Correct |
169 ms |
237324 KB |
Output is correct |
6 |
Correct |
181 ms |
237348 KB |
Output is correct |
7 |
Correct |
217 ms |
237760 KB |
Output is correct |
8 |
Correct |
162 ms |
236256 KB |
Output is correct |
9 |
Correct |
162 ms |
237360 KB |
Output is correct |
10 |
Correct |
182 ms |
237376 KB |
Output is correct |
11 |
Correct |
172 ms |
237388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
237668 KB |
Output is correct |
2 |
Correct |
216 ms |
237436 KB |
Output is correct |
3 |
Correct |
205 ms |
237668 KB |
Output is correct |
4 |
Correct |
194 ms |
237820 KB |
Output is correct |
5 |
Correct |
249 ms |
236324 KB |
Output is correct |
6 |
Correct |
211 ms |
237488 KB |
Output is correct |
7 |
Correct |
203 ms |
237488 KB |
Output is correct |
8 |
Correct |
244 ms |
237640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
234 ms |
237488 KB |
Output is correct |
2 |
Correct |
252 ms |
237748 KB |
Output is correct |
3 |
Correct |
265 ms |
237660 KB |
Output is correct |
4 |
Correct |
209 ms |
237636 KB |
Output is correct |
5 |
Correct |
193 ms |
237544 KB |
Output is correct |
6 |
Correct |
193 ms |
237576 KB |
Output is correct |
7 |
Correct |
181 ms |
237872 KB |
Output is correct |
8 |
Correct |
2 ms |
2380 KB |
Output is correct |
9 |
Correct |
4 ms |
5452 KB |
Output is correct |
10 |
Correct |
189 ms |
237360 KB |
Output is correct |
11 |
Correct |
236 ms |
237488 KB |
Output is correct |
12 |
Correct |
185 ms |
236404 KB |
Output is correct |
13 |
Correct |
206 ms |
237424 KB |
Output is correct |
14 |
Correct |
1 ms |
2380 KB |
Output is correct |
15 |
Correct |
4 ms |
5452 KB |
Output is correct |
16 |
Correct |
183 ms |
237364 KB |
Output is correct |
17 |
Correct |
247 ms |
237568 KB |
Output is correct |
18 |
Correct |
249 ms |
237636 KB |
Output is correct |
19 |
Correct |
237 ms |
237604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2380 KB |
Output is correct |
2 |
Correct |
2 ms |
2380 KB |
Output is correct |
3 |
Correct |
2 ms |
2380 KB |
Output is correct |
4 |
Correct |
2 ms |
2380 KB |
Output is correct |
5 |
Correct |
2 ms |
2380 KB |
Output is correct |
6 |
Correct |
1 ms |
2380 KB |
Output is correct |
7 |
Correct |
2 ms |
2380 KB |
Output is correct |
8 |
Correct |
1 ms |
2380 KB |
Output is correct |
9 |
Correct |
2 ms |
2380 KB |
Output is correct |
10 |
Correct |
1 ms |
844 KB |
Output is correct |
11 |
Correct |
2 ms |
2380 KB |
Output is correct |
12 |
Correct |
1 ms |
2380 KB |
Output is correct |
13 |
Correct |
5 ms |
5452 KB |
Output is correct |
14 |
Correct |
4 ms |
5452 KB |
Output is correct |
15 |
Correct |
4 ms |
5452 KB |
Output is correct |
16 |
Correct |
4 ms |
5452 KB |
Output is correct |
17 |
Correct |
4 ms |
5452 KB |
Output is correct |
18 |
Correct |
4 ms |
5452 KB |
Output is correct |
19 |
Correct |
4 ms |
5324 KB |
Output is correct |
20 |
Correct |
5 ms |
5452 KB |
Output is correct |
21 |
Correct |
4 ms |
5432 KB |
Output is correct |
22 |
Correct |
4 ms |
5452 KB |
Output is correct |
23 |
Correct |
4 ms |
5452 KB |
Output is correct |
24 |
Correct |
4 ms |
5452 KB |
Output is correct |
25 |
Correct |
177 ms |
237372 KB |
Output is correct |
26 |
Correct |
148 ms |
237380 KB |
Output is correct |
27 |
Correct |
169 ms |
237400 KB |
Output is correct |
28 |
Correct |
161 ms |
237380 KB |
Output is correct |
29 |
Correct |
169 ms |
237324 KB |
Output is correct |
30 |
Correct |
181 ms |
237348 KB |
Output is correct |
31 |
Correct |
217 ms |
237760 KB |
Output is correct |
32 |
Correct |
162 ms |
236256 KB |
Output is correct |
33 |
Correct |
162 ms |
237360 KB |
Output is correct |
34 |
Correct |
182 ms |
237376 KB |
Output is correct |
35 |
Correct |
172 ms |
237388 KB |
Output is correct |
36 |
Correct |
204 ms |
237668 KB |
Output is correct |
37 |
Correct |
216 ms |
237436 KB |
Output is correct |
38 |
Correct |
205 ms |
237668 KB |
Output is correct |
39 |
Correct |
194 ms |
237820 KB |
Output is correct |
40 |
Correct |
249 ms |
236324 KB |
Output is correct |
41 |
Correct |
211 ms |
237488 KB |
Output is correct |
42 |
Correct |
203 ms |
237488 KB |
Output is correct |
43 |
Correct |
244 ms |
237640 KB |
Output is correct |
44 |
Correct |
234 ms |
237488 KB |
Output is correct |
45 |
Correct |
252 ms |
237748 KB |
Output is correct |
46 |
Correct |
265 ms |
237660 KB |
Output is correct |
47 |
Correct |
209 ms |
237636 KB |
Output is correct |
48 |
Correct |
193 ms |
237544 KB |
Output is correct |
49 |
Correct |
193 ms |
237576 KB |
Output is correct |
50 |
Correct |
181 ms |
237872 KB |
Output is correct |
51 |
Correct |
2 ms |
2380 KB |
Output is correct |
52 |
Correct |
4 ms |
5452 KB |
Output is correct |
53 |
Correct |
189 ms |
237360 KB |
Output is correct |
54 |
Correct |
236 ms |
237488 KB |
Output is correct |
55 |
Correct |
185 ms |
236404 KB |
Output is correct |
56 |
Correct |
206 ms |
237424 KB |
Output is correct |
57 |
Correct |
1 ms |
2380 KB |
Output is correct |
58 |
Correct |
4 ms |
5452 KB |
Output is correct |
59 |
Correct |
183 ms |
237364 KB |
Output is correct |
60 |
Correct |
247 ms |
237568 KB |
Output is correct |
61 |
Correct |
249 ms |
237636 KB |
Output is correct |
62 |
Correct |
237 ms |
237604 KB |
Output is correct |
63 |
Correct |
221 ms |
237552 KB |
Output is correct |
64 |
Correct |
250 ms |
237680 KB |
Output is correct |
65 |
Correct |
252 ms |
237736 KB |
Output is correct |
66 |
Correct |
202 ms |
237472 KB |
Output is correct |
67 |
Correct |
269 ms |
237636 KB |
Output is correct |
68 |
Correct |
205 ms |
236460 KB |
Output is correct |
69 |
Correct |
209 ms |
237460 KB |
Output is correct |
70 |
Correct |
264 ms |
237536 KB |
Output is correct |
71 |
Correct |
258 ms |
237616 KB |
Output is correct |