#include <bits/stdc++.h>
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = (int) 1e5 + 5;
const int LOG = 18;
int n, k, m, q;
int lg[N];
pair<int, int> st[LOG][N];
int a[N << 1], b[N << 1];
vector<int> in[N], out[N];
struct sparse_table {
pair<int, int> spt[LOG - 1][N];
pair<int, int> cmb(pair<int, int> a, pair<int, int> b) {
return {min(a.first, b.first), max(a.second, b.second)};
}
void build(int j) {
for (int i = 1; i <= n; ++i) {
spt[0][i] = st[j][i];
}
for (int j = 1; j <= lg[n]; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
spt[j][i] = cmb(spt[j - 1][i], spt[j - 1][i + (1 << (j - 1))]);
}
}
}
pair<int, int> get(int l, int r) {
int k = lg[r - l + 1];
return cmb(spt[k][l], spt[k][r - (1 << k) + 1]);
}
} spt[LOG];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef ngu
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n >> k >> m;
vector<int> inc, dec;
for (int i = 1; i <= m; ++i) {
cin >> a[i] >> b[i];
(a[i] < b[i] ? inc : dec).emplace_back(i);
}
for (int i : inc) {
in[a[i]].emplace_back(b[i]);
out[min(b[i] - 1, a[i] + k - 1)].emplace_back(b[i]);
}
multiset<int> s;
for (int i = 1; i <= n; ++i) {
if (i > 1) {
lg[i] = lg[i / 2] + 1;
}
st[0][i] = {i, i};
for (int r : in[i]) {
s.insert(r);
}
if (s.size()) {
st[0][i].second = *s.rbegin();
}
for (int r : out[i]) {
s.erase(s.find(r));
}
in[i].clear();
out[i].clear();
}
s.clear();
for (int i : dec) {
in[a[i]].emplace_back(b[i]);
out[max(b[i] + 1, a[i] - k + 1)].emplace_back(b[i]);
}
for (int i = n; i >= 1; --i) {
for (int l : in[i]) {
s.insert(l);
}
if (s.size()) {
st[0][i].first = *s.begin();
}
for (int l : out[i]) {
s.erase(s.find(l));
}
}
spt[0].build(0);
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i <= n; ++i) {
st[j][i] = spt[j - 1].get(st[j - 1][i].first, st[j - 1][i].second);
}
spt[j].build(j);
}
auto reach = [&](pair<int, int> x, int i) -> bool {
return x.first <= i && i <= x.second;
};
cin >> q;
while (q--) {
int s, t;
cin >> s >> t;
if (reach(st[LOG - 1][s], t)) {
pair<int, int> cur = {s, s};
int res = 0;
for (int i = LOG - 2; i >= 0; --i) {
pair<int, int> new_cur = spt[i].get(cur.first, cur.second);
if (!reach(new_cur, t)) {
cur = new_cur;
res += 1 << i;
}
}
cout << res + 1 << "\n";
} else {
cout << -1 << "\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
111700 KB |
Output is correct |
2 |
Correct |
13 ms |
111708 KB |
Output is correct |
3 |
Correct |
14 ms |
113740 KB |
Output is correct |
4 |
Correct |
13 ms |
111708 KB |
Output is correct |
5 |
Correct |
13 ms |
113752 KB |
Output is correct |
6 |
Correct |
13 ms |
111708 KB |
Output is correct |
7 |
Correct |
15 ms |
115804 KB |
Output is correct |
8 |
Correct |
14 ms |
111540 KB |
Output is correct |
9 |
Correct |
14 ms |
111708 KB |
Output is correct |
10 |
Correct |
9 ms |
74584 KB |
Output is correct |
11 |
Correct |
13 ms |
107612 KB |
Output is correct |
12 |
Correct |
16 ms |
111704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
111700 KB |
Output is correct |
2 |
Correct |
13 ms |
111708 KB |
Output is correct |
3 |
Correct |
14 ms |
113740 KB |
Output is correct |
4 |
Correct |
13 ms |
111708 KB |
Output is correct |
5 |
Correct |
13 ms |
113752 KB |
Output is correct |
6 |
Correct |
13 ms |
111708 KB |
Output is correct |
7 |
Correct |
15 ms |
115804 KB |
Output is correct |
8 |
Correct |
14 ms |
111540 KB |
Output is correct |
9 |
Correct |
14 ms |
111708 KB |
Output is correct |
10 |
Correct |
9 ms |
74584 KB |
Output is correct |
11 |
Correct |
13 ms |
107612 KB |
Output is correct |
12 |
Correct |
16 ms |
111704 KB |
Output is correct |
13 |
Correct |
17 ms |
115224 KB |
Output is correct |
14 |
Correct |
16 ms |
115316 KB |
Output is correct |
15 |
Correct |
15 ms |
113244 KB |
Output is correct |
16 |
Correct |
15 ms |
113392 KB |
Output is correct |
17 |
Correct |
15 ms |
115288 KB |
Output is correct |
18 |
Correct |
15 ms |
115292 KB |
Output is correct |
19 |
Correct |
15 ms |
113244 KB |
Output is correct |
20 |
Correct |
17 ms |
115292 KB |
Output is correct |
21 |
Correct |
16 ms |
113304 KB |
Output is correct |
22 |
Correct |
15 ms |
115288 KB |
Output is correct |
23 |
Correct |
15 ms |
115372 KB |
Output is correct |
24 |
Correct |
15 ms |
115544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
255952 KB |
Output is correct |
2 |
Correct |
124 ms |
255924 KB |
Output is correct |
3 |
Correct |
118 ms |
256900 KB |
Output is correct |
4 |
Correct |
120 ms |
255696 KB |
Output is correct |
5 |
Correct |
180 ms |
258204 KB |
Output is correct |
6 |
Correct |
147 ms |
257736 KB |
Output is correct |
7 |
Correct |
164 ms |
260292 KB |
Output is correct |
8 |
Correct |
157 ms |
255776 KB |
Output is correct |
9 |
Correct |
138 ms |
257040 KB |
Output is correct |
10 |
Correct |
156 ms |
257836 KB |
Output is correct |
11 |
Correct |
173 ms |
257840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
258256 KB |
Output is correct |
2 |
Correct |
186 ms |
259196 KB |
Output is correct |
3 |
Correct |
150 ms |
258512 KB |
Output is correct |
4 |
Correct |
180 ms |
261156 KB |
Output is correct |
5 |
Correct |
243 ms |
259180 KB |
Output is correct |
6 |
Correct |
197 ms |
260216 KB |
Output is correct |
7 |
Correct |
174 ms |
257876 KB |
Output is correct |
8 |
Correct |
218 ms |
257932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
213 ms |
260040 KB |
Output is correct |
2 |
Correct |
199 ms |
258548 KB |
Output is correct |
3 |
Correct |
173 ms |
255188 KB |
Output is correct |
4 |
Correct |
150 ms |
253196 KB |
Output is correct |
5 |
Correct |
120 ms |
251988 KB |
Output is correct |
6 |
Correct |
120 ms |
251788 KB |
Output is correct |
7 |
Correct |
149 ms |
260332 KB |
Output is correct |
8 |
Correct |
15 ms |
123740 KB |
Output is correct |
9 |
Correct |
16 ms |
125276 KB |
Output is correct |
10 |
Correct |
211 ms |
260748 KB |
Output is correct |
11 |
Correct |
217 ms |
262100 KB |
Output is correct |
12 |
Correct |
226 ms |
259332 KB |
Output is correct |
13 |
Correct |
213 ms |
262060 KB |
Output is correct |
14 |
Correct |
15 ms |
123828 KB |
Output is correct |
15 |
Correct |
16 ms |
125216 KB |
Output is correct |
16 |
Correct |
160 ms |
257904 KB |
Output is correct |
17 |
Correct |
232 ms |
258192 KB |
Output is correct |
18 |
Correct |
222 ms |
258252 KB |
Output is correct |
19 |
Correct |
184 ms |
258100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
111700 KB |
Output is correct |
2 |
Correct |
13 ms |
111708 KB |
Output is correct |
3 |
Correct |
14 ms |
113740 KB |
Output is correct |
4 |
Correct |
13 ms |
111708 KB |
Output is correct |
5 |
Correct |
13 ms |
113752 KB |
Output is correct |
6 |
Correct |
13 ms |
111708 KB |
Output is correct |
7 |
Correct |
15 ms |
115804 KB |
Output is correct |
8 |
Correct |
14 ms |
111540 KB |
Output is correct |
9 |
Correct |
14 ms |
111708 KB |
Output is correct |
10 |
Correct |
9 ms |
74584 KB |
Output is correct |
11 |
Correct |
13 ms |
107612 KB |
Output is correct |
12 |
Correct |
16 ms |
111704 KB |
Output is correct |
13 |
Correct |
17 ms |
115224 KB |
Output is correct |
14 |
Correct |
16 ms |
115316 KB |
Output is correct |
15 |
Correct |
15 ms |
113244 KB |
Output is correct |
16 |
Correct |
15 ms |
113392 KB |
Output is correct |
17 |
Correct |
15 ms |
115288 KB |
Output is correct |
18 |
Correct |
15 ms |
115292 KB |
Output is correct |
19 |
Correct |
15 ms |
113244 KB |
Output is correct |
20 |
Correct |
17 ms |
115292 KB |
Output is correct |
21 |
Correct |
16 ms |
113304 KB |
Output is correct |
22 |
Correct |
15 ms |
115288 KB |
Output is correct |
23 |
Correct |
15 ms |
115372 KB |
Output is correct |
24 |
Correct |
15 ms |
115544 KB |
Output is correct |
25 |
Correct |
122 ms |
255952 KB |
Output is correct |
26 |
Correct |
124 ms |
255924 KB |
Output is correct |
27 |
Correct |
118 ms |
256900 KB |
Output is correct |
28 |
Correct |
120 ms |
255696 KB |
Output is correct |
29 |
Correct |
180 ms |
258204 KB |
Output is correct |
30 |
Correct |
147 ms |
257736 KB |
Output is correct |
31 |
Correct |
164 ms |
260292 KB |
Output is correct |
32 |
Correct |
157 ms |
255776 KB |
Output is correct |
33 |
Correct |
138 ms |
257040 KB |
Output is correct |
34 |
Correct |
156 ms |
257836 KB |
Output is correct |
35 |
Correct |
173 ms |
257840 KB |
Output is correct |
36 |
Correct |
145 ms |
258256 KB |
Output is correct |
37 |
Correct |
186 ms |
259196 KB |
Output is correct |
38 |
Correct |
150 ms |
258512 KB |
Output is correct |
39 |
Correct |
180 ms |
261156 KB |
Output is correct |
40 |
Correct |
243 ms |
259180 KB |
Output is correct |
41 |
Correct |
197 ms |
260216 KB |
Output is correct |
42 |
Correct |
174 ms |
257876 KB |
Output is correct |
43 |
Correct |
218 ms |
257932 KB |
Output is correct |
44 |
Correct |
213 ms |
260040 KB |
Output is correct |
45 |
Correct |
199 ms |
258548 KB |
Output is correct |
46 |
Correct |
173 ms |
255188 KB |
Output is correct |
47 |
Correct |
150 ms |
253196 KB |
Output is correct |
48 |
Correct |
120 ms |
251988 KB |
Output is correct |
49 |
Correct |
120 ms |
251788 KB |
Output is correct |
50 |
Correct |
149 ms |
260332 KB |
Output is correct |
51 |
Correct |
15 ms |
123740 KB |
Output is correct |
52 |
Correct |
16 ms |
125276 KB |
Output is correct |
53 |
Correct |
211 ms |
260748 KB |
Output is correct |
54 |
Correct |
217 ms |
262100 KB |
Output is correct |
55 |
Correct |
226 ms |
259332 KB |
Output is correct |
56 |
Correct |
213 ms |
262060 KB |
Output is correct |
57 |
Correct |
15 ms |
123828 KB |
Output is correct |
58 |
Correct |
16 ms |
125216 KB |
Output is correct |
59 |
Correct |
160 ms |
257904 KB |
Output is correct |
60 |
Correct |
232 ms |
258192 KB |
Output is correct |
61 |
Correct |
222 ms |
258252 KB |
Output is correct |
62 |
Correct |
184 ms |
258100 KB |
Output is correct |
63 |
Correct |
167 ms |
256596 KB |
Output is correct |
64 |
Correct |
152 ms |
257748 KB |
Output is correct |
65 |
Correct |
172 ms |
256776 KB |
Output is correct |
66 |
Correct |
214 ms |
259184 KB |
Output is correct |
67 |
Correct |
204 ms |
258756 KB |
Output is correct |
68 |
Correct |
251 ms |
257288 KB |
Output is correct |
69 |
Correct |
225 ms |
260168 KB |
Output is correct |
70 |
Correct |
210 ms |
258024 KB |
Output is correct |
71 |
Correct |
236 ms |
257872 KB |
Output is correct |