#include <bits/stdc++.h>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(x) (x).begin(), (x).end()
#define printrange(s, e) {for (auto it = s; it < e; it++) {cout << *it << ' ';} cout << '\n';}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;
#define LOCAL false
const int MAX_LOGN = 17;
const int MAX_N = 1<<MAX_LOGN; // >10^5
const int MAX_M = 2e5 + 7;
int n, k, m, q;
const int TREE_SIZE = MAX_N<<1;
int ftree[TREE_SIZE];
int btree[TREE_SIZE];
void fpushrange(int l, int r, int val) {
for (l += MAX_N, r += MAX_N+1; l<r; l>>=1, r>>=1) {
if (l&1) {
ftree[l] = max(ftree[l], val);
l++;
}
if (r&1) {
r--;
ftree[r] = max(ftree[r], val);
}
}
}
void bpushrange(int l, int r, int val) {
for (l += MAX_N, r += MAX_N+1; l<r; l>>=1, r>>=1) {
if (l&1) {
btree[l] = min(btree[l], val);
l++;
}
if (r&1) {
r--;
btree[r] = min(btree[r], val);
}
}
}
int fgetmax(int idx) {
int mx = INT_MIN;
for (int v = idx+MAX_N; v >= 1; v>>=1) mx = max(mx, ftree[v]);
return mx;
}
int bgetmin(int idx) {
int mn = INT_MAX;
for (int v = idx+MAX_N; v >= 1; v>>=1) mn = min(mn, btree[v]);
return mn;
}
pii ivl[MAX_LOGN+1][TREE_SIZE];
pii* curtree;
void build() {
int l, r;
for (int v = MAX_N-1; v >= 1; v--) {
l = v*2; r = v*2+1;
curtree[v].first = min(curtree[l].first, curtree[r].first);
curtree[v].second = max(curtree[l].second, curtree[r].second);
}
}
pii getrange(int l, int r) {
int s = INT_MAX;
int e = INT_MIN;
for (l += MAX_N, r += MAX_N+1; l<r; l>>=1, r>>=1) {
if (l&1) {
s = min(s, curtree[l].first);
e = max(e, curtree[l].second);
l++;
}
if (r&1) {
r--;
s = min(s, curtree[r].first);
e = max(e, curtree[r].second);
}
}
return {s, e};
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
if (LOCAL) {
ignore=freopen("io/in", "r", stdin);
ignore=freopen("io/out", "w", stdout);
}
rep(i, TREE_SIZE) {
ftree[i] = INT_MIN;
btree[i] = INT_MAX;
}
cin >> n >> k;
cin >> m;
int a, b;
rep(i, m) {
cin >> a >> b;
a--; b--;
if (a < b) fpushrange(a, min(a+k-1, b-1), b);
else bpushrange(max(a-k+1, b+1), a, b);
}
curtree = ivl[0];
rep(i, n) curtree[MAX_N+i] = {min(i, bgetmin(i)), max(i, fgetmax(i))};
build();
rep1(i, MAX_LOGN) {
rep(v, MAX_N) {
curtree = ivl[i-1];
auto [l, r] = ivl[i-1][MAX_N+v];
ivl[i][MAX_N+v] = getrange(l, r);
}
curtree = ivl[i];
build();
}
cin >> q;
rep(i, q) {
int l, r;
int ans = 0;
bool can = false;
cin >> a >> b;
a--; b--;
l = a; r = a;
for (int p = MAX_LOGN; p >= 0; p--) {
curtree = ivl[p];
auto [l2, r2] = getrange(l, r);
if (!(l2 <= b && b <= r2)) {
l = l2;
r = r2;
ans |= (1<<p);
} else can = true;
}
if (can) cout << ans+1 << '\n';
else cout << "-1\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
39260 KB |
Output is correct |
2 |
Correct |
21 ms |
39544 KB |
Output is correct |
3 |
Correct |
36 ms |
39252 KB |
Output is correct |
4 |
Correct |
32 ms |
39252 KB |
Output is correct |
5 |
Correct |
31 ms |
39188 KB |
Output is correct |
6 |
Correct |
43 ms |
39248 KB |
Output is correct |
7 |
Correct |
15 ms |
39256 KB |
Output is correct |
8 |
Correct |
35 ms |
39252 KB |
Output is correct |
9 |
Correct |
35 ms |
39452 KB |
Output is correct |
10 |
Correct |
15 ms |
39260 KB |
Output is correct |
11 |
Correct |
37 ms |
39432 KB |
Output is correct |
12 |
Correct |
30 ms |
39172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
39260 KB |
Output is correct |
2 |
Correct |
21 ms |
39544 KB |
Output is correct |
3 |
Correct |
36 ms |
39252 KB |
Output is correct |
4 |
Correct |
32 ms |
39252 KB |
Output is correct |
5 |
Correct |
31 ms |
39188 KB |
Output is correct |
6 |
Correct |
43 ms |
39248 KB |
Output is correct |
7 |
Correct |
15 ms |
39256 KB |
Output is correct |
8 |
Correct |
35 ms |
39252 KB |
Output is correct |
9 |
Correct |
35 ms |
39452 KB |
Output is correct |
10 |
Correct |
15 ms |
39260 KB |
Output is correct |
11 |
Correct |
37 ms |
39432 KB |
Output is correct |
12 |
Correct |
30 ms |
39172 KB |
Output is correct |
13 |
Correct |
52 ms |
39412 KB |
Output is correct |
14 |
Correct |
43 ms |
39248 KB |
Output is correct |
15 |
Correct |
41 ms |
39432 KB |
Output is correct |
16 |
Correct |
37 ms |
39252 KB |
Output is correct |
17 |
Correct |
20 ms |
39256 KB |
Output is correct |
18 |
Correct |
48 ms |
39412 KB |
Output is correct |
19 |
Correct |
39 ms |
39420 KB |
Output is correct |
20 |
Correct |
38 ms |
39456 KB |
Output is correct |
21 |
Correct |
16 ms |
39256 KB |
Output is correct |
22 |
Correct |
50 ms |
39428 KB |
Output is correct |
23 |
Correct |
31 ms |
39248 KB |
Output is correct |
24 |
Correct |
19 ms |
39260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
40268 KB |
Output is correct |
2 |
Correct |
125 ms |
40584 KB |
Output is correct |
3 |
Correct |
144 ms |
40488 KB |
Output is correct |
4 |
Correct |
112 ms |
40024 KB |
Output is correct |
5 |
Correct |
99 ms |
41724 KB |
Output is correct |
6 |
Correct |
100 ms |
41952 KB |
Output is correct |
7 |
Correct |
88 ms |
41552 KB |
Output is correct |
8 |
Correct |
81 ms |
40540 KB |
Output is correct |
9 |
Correct |
73 ms |
40532 KB |
Output is correct |
10 |
Correct |
102 ms |
41728 KB |
Output is correct |
11 |
Correct |
107 ms |
41592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
172 ms |
40920 KB |
Output is correct |
2 |
Correct |
151 ms |
42244 KB |
Output is correct |
3 |
Correct |
291 ms |
41344 KB |
Output is correct |
4 |
Correct |
109 ms |
41812 KB |
Output is correct |
5 |
Correct |
122 ms |
42120 KB |
Output is correct |
6 |
Correct |
133 ms |
42484 KB |
Output is correct |
7 |
Correct |
159 ms |
42324 KB |
Output is correct |
8 |
Correct |
176 ms |
42232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
42432 KB |
Output is correct |
2 |
Correct |
276 ms |
41392 KB |
Output is correct |
3 |
Correct |
272 ms |
40932 KB |
Output is correct |
4 |
Correct |
235 ms |
40272 KB |
Output is correct |
5 |
Correct |
151 ms |
40016 KB |
Output is correct |
6 |
Correct |
215 ms |
40116 KB |
Output is correct |
7 |
Correct |
178 ms |
41092 KB |
Output is correct |
8 |
Correct |
37 ms |
39252 KB |
Output is correct |
9 |
Correct |
50 ms |
39424 KB |
Output is correct |
10 |
Correct |
176 ms |
41556 KB |
Output is correct |
11 |
Correct |
198 ms |
42104 KB |
Output is correct |
12 |
Correct |
217 ms |
42200 KB |
Output is correct |
13 |
Correct |
221 ms |
42164 KB |
Output is correct |
14 |
Correct |
16 ms |
39260 KB |
Output is correct |
15 |
Correct |
19 ms |
39260 KB |
Output is correct |
16 |
Correct |
136 ms |
41608 KB |
Output is correct |
17 |
Correct |
297 ms |
42468 KB |
Output is correct |
18 |
Correct |
281 ms |
42412 KB |
Output is correct |
19 |
Correct |
250 ms |
42360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
39260 KB |
Output is correct |
2 |
Correct |
21 ms |
39544 KB |
Output is correct |
3 |
Correct |
36 ms |
39252 KB |
Output is correct |
4 |
Correct |
32 ms |
39252 KB |
Output is correct |
5 |
Correct |
31 ms |
39188 KB |
Output is correct |
6 |
Correct |
43 ms |
39248 KB |
Output is correct |
7 |
Correct |
15 ms |
39256 KB |
Output is correct |
8 |
Correct |
35 ms |
39252 KB |
Output is correct |
9 |
Correct |
35 ms |
39452 KB |
Output is correct |
10 |
Correct |
15 ms |
39260 KB |
Output is correct |
11 |
Correct |
37 ms |
39432 KB |
Output is correct |
12 |
Correct |
30 ms |
39172 KB |
Output is correct |
13 |
Correct |
52 ms |
39412 KB |
Output is correct |
14 |
Correct |
43 ms |
39248 KB |
Output is correct |
15 |
Correct |
41 ms |
39432 KB |
Output is correct |
16 |
Correct |
37 ms |
39252 KB |
Output is correct |
17 |
Correct |
20 ms |
39256 KB |
Output is correct |
18 |
Correct |
48 ms |
39412 KB |
Output is correct |
19 |
Correct |
39 ms |
39420 KB |
Output is correct |
20 |
Correct |
38 ms |
39456 KB |
Output is correct |
21 |
Correct |
16 ms |
39256 KB |
Output is correct |
22 |
Correct |
50 ms |
39428 KB |
Output is correct |
23 |
Correct |
31 ms |
39248 KB |
Output is correct |
24 |
Correct |
19 ms |
39260 KB |
Output is correct |
25 |
Correct |
115 ms |
40268 KB |
Output is correct |
26 |
Correct |
125 ms |
40584 KB |
Output is correct |
27 |
Correct |
144 ms |
40488 KB |
Output is correct |
28 |
Correct |
112 ms |
40024 KB |
Output is correct |
29 |
Correct |
99 ms |
41724 KB |
Output is correct |
30 |
Correct |
100 ms |
41952 KB |
Output is correct |
31 |
Correct |
88 ms |
41552 KB |
Output is correct |
32 |
Correct |
81 ms |
40540 KB |
Output is correct |
33 |
Correct |
73 ms |
40532 KB |
Output is correct |
34 |
Correct |
102 ms |
41728 KB |
Output is correct |
35 |
Correct |
107 ms |
41592 KB |
Output is correct |
36 |
Correct |
172 ms |
40920 KB |
Output is correct |
37 |
Correct |
151 ms |
42244 KB |
Output is correct |
38 |
Correct |
291 ms |
41344 KB |
Output is correct |
39 |
Correct |
109 ms |
41812 KB |
Output is correct |
40 |
Correct |
122 ms |
42120 KB |
Output is correct |
41 |
Correct |
133 ms |
42484 KB |
Output is correct |
42 |
Correct |
159 ms |
42324 KB |
Output is correct |
43 |
Correct |
176 ms |
42232 KB |
Output is correct |
44 |
Correct |
350 ms |
42432 KB |
Output is correct |
45 |
Correct |
276 ms |
41392 KB |
Output is correct |
46 |
Correct |
272 ms |
40932 KB |
Output is correct |
47 |
Correct |
235 ms |
40272 KB |
Output is correct |
48 |
Correct |
151 ms |
40016 KB |
Output is correct |
49 |
Correct |
215 ms |
40116 KB |
Output is correct |
50 |
Correct |
178 ms |
41092 KB |
Output is correct |
51 |
Correct |
37 ms |
39252 KB |
Output is correct |
52 |
Correct |
50 ms |
39424 KB |
Output is correct |
53 |
Correct |
176 ms |
41556 KB |
Output is correct |
54 |
Correct |
198 ms |
42104 KB |
Output is correct |
55 |
Correct |
217 ms |
42200 KB |
Output is correct |
56 |
Correct |
221 ms |
42164 KB |
Output is correct |
57 |
Correct |
16 ms |
39260 KB |
Output is correct |
58 |
Correct |
19 ms |
39260 KB |
Output is correct |
59 |
Correct |
136 ms |
41608 KB |
Output is correct |
60 |
Correct |
297 ms |
42468 KB |
Output is correct |
61 |
Correct |
281 ms |
42412 KB |
Output is correct |
62 |
Correct |
250 ms |
42360 KB |
Output is correct |
63 |
Correct |
245 ms |
40952 KB |
Output is correct |
64 |
Correct |
270 ms |
41288 KB |
Output is correct |
65 |
Correct |
259 ms |
41300 KB |
Output is correct |
66 |
Correct |
157 ms |
42368 KB |
Output is correct |
67 |
Correct |
215 ms |
42328 KB |
Output is correct |
68 |
Correct |
145 ms |
42324 KB |
Output is correct |
69 |
Correct |
124 ms |
42208 KB |
Output is correct |
70 |
Correct |
171 ms |
42324 KB |
Output is correct |
71 |
Correct |
249 ms |
42360 KB |
Output is correct |