#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define double long double
using pii = pair<int, int>;
template <typename T>
using Prior = std::priority_queue<T>;
template <typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define X first
#define Y second
#define ee emplace
#define eb emplace_back
#define ef push_front
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#ifdef local
#define fastIO() void()
#define debug(...) \
cerr << "\u001b[33m" << "At func " << __FUNCTION__ << ", line " << __LINE__ << ": ",\
cerr << "(" << #__VA_ARGS__ << ") = ",\
_do(__VA_ARGS__),\
cerr << "\u001b[0m"
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif
template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}
void chminmax(pii &lhs, pii rhs) {chmin(lhs.X, rhs.X), chmax(lhs.Y, rhs.Y);}
const int INF = INT_MAX;
const int lgmx = 17 + 1;
const int maxn = 1 << 17;
vector<int> tag_mx(maxn<<1, -1), tag_mn(maxn<<1, maxn);
vector<int> L(maxn), R(maxn), dis(maxn);
vector<vector<pii>> jump(lgmx, vector<pii>(maxn, {maxn, -1}));
vector<vector<pii>> seg(lgmx, vector<pii>(maxn<<1, {maxn, -1}));
void seg_modify_range_max(int qL, int qR, int val, int now = 1, int nL = 0, int nR = maxn-1) {
if (qL <= nL and nR <= qR) return chmax(tag_mx[now], val), void();
int nM = (nL + nR) >> 1;
if (qL <= nM) seg_modify_range_max(qL, qR, val, now<<1, nL, nM);
if (qR > nM) seg_modify_range_max(qL, qR, val, now<<1|1, nM+1, nR);
}
void seg_modify_range_min(int qL, int qR, int val, int now = 1, int nL = 0, int nR = maxn-1) {
if (qL <= nL and nR <= qR) return chmin(tag_mn[now], val), void();
int nM = (nL + nR) >> 1;
if (qL <= nM) seg_modify_range_min(qL, qR, val, now<<1, nL, nM);
if (qR > nM) seg_modify_range_min(qL, qR, val, now<<1|1, nM+1, nR);
}
void seg_push_tags() {
for (int i = 1; i < maxn; ++i) {
chmax(tag_mx[i<<1], tag_mx[i]), chmax(tag_mx[i<<1|1], tag_mx[i]);
chmin(tag_mn[i<<1], tag_mn[i]), chmin(tag_mn[i<<1|1], tag_mn[i]);
}
}
void seg_build() {
for (int i = 0; i < maxn; ++i) tag_mx[i+maxn] = tag_mn[i+maxn] = i;
}
pii jump_query_range_minmax(int lay, pii q, int now = 1, int nL = 0, int nR = maxn-1) {
if (q.X <= nL and nR <= q.Y) return seg[lay][now];
int nM = (nL + nR) >> 1;
pii ans = q;
if (q.X <= nM) chminmax(ans, jump_query_range_minmax(lay, q, now<<1, nL, nM));
if (q.Y > nM) chminmax(ans, jump_query_range_minmax(lay, q, now<<1|1, nM+1, nR));
return ans;
}
void jump_build() {
for (int i = 0; i < maxn; ++i) seg[0][i+maxn] = jump[0][i] = {tag_mn[i+maxn], tag_mx[i+maxn]};
for (int lay = 0; lay < lgmx; ++lay) {
if (lay) {
for (int i = 0; i < maxn; ++i) {
seg[lay][i+maxn] = jump[lay][i] = jump_query_range_minmax(lay-1, jump[lay-1][i]);
}
}
for (int i = maxn-1; i >= 1; --i) {
chminmax(seg[lay][i], seg[lay][i<<1]), chminmax(seg[lay][i], seg[lay][i<<1|1]);
}
}
}
void solve() {
int N, K, M; cin >> N >> K >> M, seg_build();
vector<pii> train(M);
for (auto &[u, v] : train) {
cin >> u >> v, --u, --v;
if (u < v) seg_modify_range_max(u, u+K-1, v);
if (u > v) seg_modify_range_min(u-K+1, u, v);
}
seg_push_tags();
jump_build();
// for (int lay = 0; lay <= 3; ++lay) {
// for (int i = 0; i < 8; ++i) debug(lay, i, jump[lay][i].X, jump[lay][i].Y);
// }
int Q; cin >> Q;
vector<pii> query(Q);
for (auto &[s, t] : query) {
cin >> s >> t, --s, --t;
int ans = 0;
pii now = {s, s}, tmp;
for (int lay = lgmx-1; lay >= 0; --lay) {
tmp = jump_query_range_minmax(lay, now);
// debug(lay, now.X, now.Y, tmp.X, tmp.Y);
if (tmp.X > t or tmp.Y < t) chminmax(now, tmp), ans += 1 << lay;
}
cout << (ans < N ? ans+1 : -1) << "\n";
}
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
287 ms |
122444 KB |
Output is correct |
2 |
Correct |
324 ms |
122544 KB |
Output is correct |
3 |
Correct |
310 ms |
122456 KB |
Output is correct |
4 |
Correct |
286 ms |
122444 KB |
Output is correct |
5 |
Correct |
322 ms |
122480 KB |
Output is correct |
6 |
Correct |
305 ms |
122480 KB |
Output is correct |
7 |
Correct |
308 ms |
122464 KB |
Output is correct |
8 |
Correct |
313 ms |
122416 KB |
Output is correct |
9 |
Correct |
278 ms |
122456 KB |
Output is correct |
10 |
Correct |
281 ms |
122476 KB |
Output is correct |
11 |
Correct |
280 ms |
122432 KB |
Output is correct |
12 |
Correct |
289 ms |
122488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
287 ms |
122444 KB |
Output is correct |
2 |
Correct |
324 ms |
122544 KB |
Output is correct |
3 |
Correct |
310 ms |
122456 KB |
Output is correct |
4 |
Correct |
286 ms |
122444 KB |
Output is correct |
5 |
Correct |
322 ms |
122480 KB |
Output is correct |
6 |
Correct |
305 ms |
122480 KB |
Output is correct |
7 |
Correct |
308 ms |
122464 KB |
Output is correct |
8 |
Correct |
313 ms |
122416 KB |
Output is correct |
9 |
Correct |
278 ms |
122456 KB |
Output is correct |
10 |
Correct |
281 ms |
122476 KB |
Output is correct |
11 |
Correct |
280 ms |
122432 KB |
Output is correct |
12 |
Correct |
289 ms |
122488 KB |
Output is correct |
13 |
Correct |
263 ms |
122432 KB |
Output is correct |
14 |
Correct |
304 ms |
122456 KB |
Output is correct |
15 |
Correct |
284 ms |
122528 KB |
Output is correct |
16 |
Correct |
318 ms |
122436 KB |
Output is correct |
17 |
Correct |
301 ms |
122416 KB |
Output is correct |
18 |
Correct |
285 ms |
122432 KB |
Output is correct |
19 |
Correct |
293 ms |
122532 KB |
Output is correct |
20 |
Correct |
285 ms |
122496 KB |
Output is correct |
21 |
Correct |
291 ms |
122472 KB |
Output is correct |
22 |
Correct |
283 ms |
122520 KB |
Output is correct |
23 |
Correct |
281 ms |
122432 KB |
Output is correct |
24 |
Correct |
306 ms |
122432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
484 ms |
122432 KB |
Output is correct |
2 |
Correct |
467 ms |
122472 KB |
Output is correct |
3 |
Correct |
514 ms |
122416 KB |
Output is correct |
4 |
Correct |
457 ms |
122432 KB |
Output is correct |
5 |
Correct |
395 ms |
122464 KB |
Output is correct |
6 |
Correct |
459 ms |
122488 KB |
Output is correct |
7 |
Correct |
304 ms |
122436 KB |
Output is correct |
8 |
Correct |
296 ms |
122468 KB |
Output is correct |
9 |
Correct |
252 ms |
122432 KB |
Output is correct |
10 |
Correct |
512 ms |
122516 KB |
Output is correct |
11 |
Correct |
489 ms |
122524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
556 ms |
122540 KB |
Output is correct |
2 |
Correct |
567 ms |
122532 KB |
Output is correct |
3 |
Correct |
766 ms |
122440 KB |
Output is correct |
4 |
Correct |
505 ms |
122460 KB |
Output is correct |
5 |
Correct |
389 ms |
122508 KB |
Output is correct |
6 |
Correct |
395 ms |
122456 KB |
Output is correct |
7 |
Correct |
607 ms |
122552 KB |
Output is correct |
8 |
Correct |
624 ms |
122620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
716 ms |
122516 KB |
Output is correct |
2 |
Correct |
710 ms |
122412 KB |
Output is correct |
3 |
Correct |
690 ms |
122448 KB |
Output is correct |
4 |
Correct |
643 ms |
122456 KB |
Output is correct |
5 |
Correct |
494 ms |
122432 KB |
Output is correct |
6 |
Correct |
558 ms |
122500 KB |
Output is correct |
7 |
Correct |
518 ms |
122560 KB |
Output is correct |
8 |
Correct |
246 ms |
122488 KB |
Output is correct |
9 |
Correct |
272 ms |
122520 KB |
Output is correct |
10 |
Correct |
448 ms |
122512 KB |
Output is correct |
11 |
Correct |
499 ms |
122440 KB |
Output is correct |
12 |
Correct |
544 ms |
122532 KB |
Output is correct |
13 |
Correct |
534 ms |
122432 KB |
Output is correct |
14 |
Correct |
251 ms |
122480 KB |
Output is correct |
15 |
Correct |
247 ms |
122508 KB |
Output is correct |
16 |
Correct |
416 ms |
122432 KB |
Output is correct |
17 |
Correct |
687 ms |
122596 KB |
Output is correct |
18 |
Correct |
639 ms |
122596 KB |
Output is correct |
19 |
Correct |
600 ms |
122564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
287 ms |
122444 KB |
Output is correct |
2 |
Correct |
324 ms |
122544 KB |
Output is correct |
3 |
Correct |
310 ms |
122456 KB |
Output is correct |
4 |
Correct |
286 ms |
122444 KB |
Output is correct |
5 |
Correct |
322 ms |
122480 KB |
Output is correct |
6 |
Correct |
305 ms |
122480 KB |
Output is correct |
7 |
Correct |
308 ms |
122464 KB |
Output is correct |
8 |
Correct |
313 ms |
122416 KB |
Output is correct |
9 |
Correct |
278 ms |
122456 KB |
Output is correct |
10 |
Correct |
281 ms |
122476 KB |
Output is correct |
11 |
Correct |
280 ms |
122432 KB |
Output is correct |
12 |
Correct |
289 ms |
122488 KB |
Output is correct |
13 |
Correct |
263 ms |
122432 KB |
Output is correct |
14 |
Correct |
304 ms |
122456 KB |
Output is correct |
15 |
Correct |
284 ms |
122528 KB |
Output is correct |
16 |
Correct |
318 ms |
122436 KB |
Output is correct |
17 |
Correct |
301 ms |
122416 KB |
Output is correct |
18 |
Correct |
285 ms |
122432 KB |
Output is correct |
19 |
Correct |
293 ms |
122532 KB |
Output is correct |
20 |
Correct |
285 ms |
122496 KB |
Output is correct |
21 |
Correct |
291 ms |
122472 KB |
Output is correct |
22 |
Correct |
283 ms |
122520 KB |
Output is correct |
23 |
Correct |
281 ms |
122432 KB |
Output is correct |
24 |
Correct |
306 ms |
122432 KB |
Output is correct |
25 |
Correct |
484 ms |
122432 KB |
Output is correct |
26 |
Correct |
467 ms |
122472 KB |
Output is correct |
27 |
Correct |
514 ms |
122416 KB |
Output is correct |
28 |
Correct |
457 ms |
122432 KB |
Output is correct |
29 |
Correct |
395 ms |
122464 KB |
Output is correct |
30 |
Correct |
459 ms |
122488 KB |
Output is correct |
31 |
Correct |
304 ms |
122436 KB |
Output is correct |
32 |
Correct |
296 ms |
122468 KB |
Output is correct |
33 |
Correct |
252 ms |
122432 KB |
Output is correct |
34 |
Correct |
512 ms |
122516 KB |
Output is correct |
35 |
Correct |
489 ms |
122524 KB |
Output is correct |
36 |
Correct |
556 ms |
122540 KB |
Output is correct |
37 |
Correct |
567 ms |
122532 KB |
Output is correct |
38 |
Correct |
766 ms |
122440 KB |
Output is correct |
39 |
Correct |
505 ms |
122460 KB |
Output is correct |
40 |
Correct |
389 ms |
122508 KB |
Output is correct |
41 |
Correct |
395 ms |
122456 KB |
Output is correct |
42 |
Correct |
607 ms |
122552 KB |
Output is correct |
43 |
Correct |
624 ms |
122620 KB |
Output is correct |
44 |
Correct |
716 ms |
122516 KB |
Output is correct |
45 |
Correct |
710 ms |
122412 KB |
Output is correct |
46 |
Correct |
690 ms |
122448 KB |
Output is correct |
47 |
Correct |
643 ms |
122456 KB |
Output is correct |
48 |
Correct |
494 ms |
122432 KB |
Output is correct |
49 |
Correct |
558 ms |
122500 KB |
Output is correct |
50 |
Correct |
518 ms |
122560 KB |
Output is correct |
51 |
Correct |
246 ms |
122488 KB |
Output is correct |
52 |
Correct |
272 ms |
122520 KB |
Output is correct |
53 |
Correct |
448 ms |
122512 KB |
Output is correct |
54 |
Correct |
499 ms |
122440 KB |
Output is correct |
55 |
Correct |
544 ms |
122532 KB |
Output is correct |
56 |
Correct |
534 ms |
122432 KB |
Output is correct |
57 |
Correct |
251 ms |
122480 KB |
Output is correct |
58 |
Correct |
247 ms |
122508 KB |
Output is correct |
59 |
Correct |
416 ms |
122432 KB |
Output is correct |
60 |
Correct |
687 ms |
122596 KB |
Output is correct |
61 |
Correct |
639 ms |
122596 KB |
Output is correct |
62 |
Correct |
600 ms |
122564 KB |
Output is correct |
63 |
Correct |
641 ms |
122448 KB |
Output is correct |
64 |
Correct |
767 ms |
122440 KB |
Output is correct |
65 |
Correct |
653 ms |
122476 KB |
Output is correct |
66 |
Correct |
425 ms |
122432 KB |
Output is correct |
67 |
Correct |
589 ms |
122752 KB |
Output is correct |
68 |
Correct |
418 ms |
122432 KB |
Output is correct |
69 |
Correct |
382 ms |
122432 KB |
Output is correct |
70 |
Correct |
554 ms |
122536 KB |
Output is correct |
71 |
Correct |
684 ms |
122552 KB |
Output is correct |