//
// Created by 42kangaroo on 16/03/2023.
//
#include "bits/stdc++.h"
using namespace std;
template<typename T>
using g_t = vector<vector<T>>;
vector<int> logt;
vector<int> p2;
struct Train {
int last, en;
};
struct BinJu {
g_t<int> forWBinJ;
g_t<vector<int>> spTForw;
g_t<int> baWBinJ;
g_t<vector<int>> spTBa;
};
vector<int> makeMaxDist(g_t<Train> &ne, bool forw) {
vector<int> nex(ne.size());
std::iota(nex.begin(), nex.end(), 0);
auto comp = [&](const Train &l, const Train &r) { return (forw ? l.en < r.en : l.en > r.en); };
priority_queue<Train, vector<Train>, decltype(comp)> p(comp);
for (int i = (forw ? 0 : (int) ne.size() - 1); (forw ? i < ne.size() : i >= 0); (forw ? ++i : --i)) {
for (auto &t: ne[i]) {
p.push(t);
}
while (!p.empty() && (forw ? p.top().last < i : p.top().last > i)) p.pop();
if (!p.empty()) nex[i] = p.top().en;
}
return nex;
}
void logT(int n) {
logt = vector<int>(n + 1, 0);
for (int i = 2; i <= n; ++i) {
logt[i] = logt[i / 2] + 1;
}
}
g_t<int> sparseT(vector<int> &vals, bool ma) {
g_t<int> spT(logt[vals.size()] + 1, vector<int>(vals.size()));
spT[0] = vals;
for (int i = 1; i < spT.size(); ++i) {
for (int j = 0; j < spT[i].size() - p2[i] + 1; ++j) {
spT[i][j] = ma ? max(spT[i - 1][j], spT[i - 1][j + p2[i - 1]]) :
min(spT[i - 1][j], spT[i - 1][j + p2[i - 1]]);
}
}
return spT;
}
int mi(int a, int b, g_t<int> &spT, bool ma) {
return ma ? max(spT[logt[b - a + 1]][a], spT[logt[b - a + 1]][b - p2[logt[b - a + 1]] + 1]) :
min(spT[logt[b - a + 1]][a], spT[logt[b - a + 1]][b - p2[logt[b - a + 1]] + 1]);
}
BinJu binJ(vector<int> &forw, vector<int> &back) {
g_t<int> forWBinJ(logt[forw.size()] + 2, vector<int>(forw.size(), 0));
g_t<vector<int>> spTForw(logt[forw.size()] + 2);
g_t<int> baWBinJ(logt[forw.size()] + 2, vector<int>(forw.size(), 0));
g_t<vector<int>> spTBa(logt[forw.size()] + 2);
forWBinJ[0] = forw;
baWBinJ[0] = back;
spTForw[0] = sparseT(forw, true);
spTBa[0] = sparseT(back, false);
for (int i = 1; i < forWBinJ.size(); ++i) {
for (int j = 0; j < forw.size(); ++j) {
forWBinJ[i][j] = mi(baWBinJ[i - 1][j], forWBinJ[i - 1][j], spTForw[i - 1], true);
baWBinJ[i][j] = mi(baWBinJ[i - 1][j], forWBinJ[i - 1][j], spTBa[i - 1], false);
}
spTForw[i] = sparseT(forWBinJ[i], true);
spTBa[i] = sparseT(baWBinJ[i], false);
}
return {forWBinJ, spTForw, baWBinJ, spTBa};
}
int co(int a, int b, BinJu& binJ) {
if (a == b) return 0;
int actF=a, actB=a;
int ans = 1;
for (int i = binJ.baWBinJ.size() - 1; i >= 0; --i) {
int nF = mi(actB, actF, binJ.spTForw[i], true);
int nB = mi(actB, actF, binJ.spTBa[i], false);
if (a < b && nF < b) {
actF = nF;actB = nB;
ans += p2[i];
} else if (a > b && nB > b) {
actF = nF;actB = nB;
ans += p2[i];
}
}
return ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, r;
cin >> n >> r >> m;
logT(n);
for (int i = 1; i < 2*n; i <<= 1) {
p2.push_back(i);
}
g_t<Train> forw(n), backw(n);
for (int i = 0; i < m; ++i) {
int s, e;
cin >> s >> e;
--s;
--e;
if (s < e) {
forw[s].push_back({min(s + r - 1, e), e});
} else {
backw[s].push_back({max(s - r + 1, e), e});
}
}
vector<int> neFo = makeMaxDist(forw, true), neBa = makeMaxDist(backw, false);
auto BinJ = binJ(neFo, neBa);
int q;
cin >> q;
while(q--) {
int s, t;
cin >> s >> t;
--s;--t;
int ans = co(s, t, BinJ);
if (ans > n) cout << "-1\n";
else cout << ans << "\n";
}
}
/*20 5
10
1 9
3 12
8 18
14 18
15 20
9 1
12 3
18 8
18 14
20 15*/
Compilation message
Main.cpp: In function 'std::vector<int> makeMaxDist(g_t<Train>&, bool)':
Main.cpp:30:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Train, std::allocator<Train> >, std::allocator<std::vector<Train, std::allocator<Train> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = (forw ? 0 : (int) ne.size() - 1); (forw ? i < ne.size() : i >= 0); (forw ? ++i : --i)) {
| ~~^~~~~~~~~~~
Main.cpp: In function 'g_t<int> sparseT(std::vector<int>&, bool)':
Main.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int>, std::allocator<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 1; i < spT.size(); ++i) {
| ~~^~~~~~~~~~~~
Main.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int j = 0; j < spT[i].size() - p2[i] + 1; ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'BinJu binJ(std::vector<int>&, std::vector<int>&)':
Main.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int>, std::allocator<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 1; i < forWBinJ.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~
Main.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int j = 0; j < forw.size(); ++j) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
5 ms |
4948 KB |
Output is correct |
14 |
Correct |
5 ms |
4948 KB |
Output is correct |
15 |
Correct |
4 ms |
4948 KB |
Output is correct |
16 |
Correct |
5 ms |
4948 KB |
Output is correct |
17 |
Correct |
5 ms |
4948 KB |
Output is correct |
18 |
Correct |
5 ms |
4948 KB |
Output is correct |
19 |
Correct |
5 ms |
4692 KB |
Output is correct |
20 |
Correct |
4 ms |
4948 KB |
Output is correct |
21 |
Correct |
6 ms |
4948 KB |
Output is correct |
22 |
Correct |
5 ms |
4948 KB |
Output is correct |
23 |
Correct |
5 ms |
4948 KB |
Output is correct |
24 |
Correct |
5 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
346 ms |
517312 KB |
Output is correct |
2 |
Correct |
334 ms |
517156 KB |
Output is correct |
3 |
Correct |
321 ms |
517948 KB |
Output is correct |
4 |
Correct |
321 ms |
516968 KB |
Output is correct |
5 |
Correct |
400 ms |
520072 KB |
Output is correct |
6 |
Correct |
402 ms |
522488 KB |
Output is correct |
7 |
Correct |
385 ms |
522008 KB |
Output is correct |
8 |
Correct |
318 ms |
512180 KB |
Output is correct |
9 |
Correct |
338 ms |
517328 KB |
Output is correct |
10 |
Correct |
371 ms |
520456 KB |
Output is correct |
11 |
Correct |
372 ms |
520360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
387 ms |
517964 KB |
Output is correct |
2 |
Correct |
406 ms |
520816 KB |
Output is correct |
3 |
Correct |
409 ms |
518888 KB |
Output is correct |
4 |
Correct |
395 ms |
522732 KB |
Output is correct |
5 |
Correct |
375 ms |
515508 KB |
Output is correct |
6 |
Correct |
379 ms |
520660 KB |
Output is correct |
7 |
Correct |
439 ms |
520724 KB |
Output is correct |
8 |
Correct |
436 ms |
521036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
439 ms |
520268 KB |
Output is correct |
2 |
Correct |
430 ms |
518880 KB |
Output is correct |
3 |
Correct |
419 ms |
516824 KB |
Output is correct |
4 |
Correct |
393 ms |
514796 KB |
Output is correct |
5 |
Correct |
365 ms |
514252 KB |
Output is correct |
6 |
Correct |
351 ms |
513916 KB |
Output is correct |
7 |
Correct |
396 ms |
518760 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
5 ms |
4948 KB |
Output is correct |
10 |
Correct |
360 ms |
519516 KB |
Output is correct |
11 |
Correct |
385 ms |
520088 KB |
Output is correct |
12 |
Correct |
409 ms |
514968 KB |
Output is correct |
13 |
Correct |
448 ms |
520020 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
5 ms |
4948 KB |
Output is correct |
16 |
Correct |
365 ms |
519740 KB |
Output is correct |
17 |
Correct |
460 ms |
520400 KB |
Output is correct |
18 |
Correct |
441 ms |
520392 KB |
Output is correct |
19 |
Correct |
421 ms |
520424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
5 ms |
4948 KB |
Output is correct |
14 |
Correct |
5 ms |
4948 KB |
Output is correct |
15 |
Correct |
4 ms |
4948 KB |
Output is correct |
16 |
Correct |
5 ms |
4948 KB |
Output is correct |
17 |
Correct |
5 ms |
4948 KB |
Output is correct |
18 |
Correct |
5 ms |
4948 KB |
Output is correct |
19 |
Correct |
5 ms |
4692 KB |
Output is correct |
20 |
Correct |
4 ms |
4948 KB |
Output is correct |
21 |
Correct |
6 ms |
4948 KB |
Output is correct |
22 |
Correct |
5 ms |
4948 KB |
Output is correct |
23 |
Correct |
5 ms |
4948 KB |
Output is correct |
24 |
Correct |
5 ms |
4948 KB |
Output is correct |
25 |
Correct |
346 ms |
517312 KB |
Output is correct |
26 |
Correct |
334 ms |
517156 KB |
Output is correct |
27 |
Correct |
321 ms |
517948 KB |
Output is correct |
28 |
Correct |
321 ms |
516968 KB |
Output is correct |
29 |
Correct |
400 ms |
520072 KB |
Output is correct |
30 |
Correct |
402 ms |
522488 KB |
Output is correct |
31 |
Correct |
385 ms |
522008 KB |
Output is correct |
32 |
Correct |
318 ms |
512180 KB |
Output is correct |
33 |
Correct |
338 ms |
517328 KB |
Output is correct |
34 |
Correct |
371 ms |
520456 KB |
Output is correct |
35 |
Correct |
372 ms |
520360 KB |
Output is correct |
36 |
Correct |
387 ms |
517964 KB |
Output is correct |
37 |
Correct |
406 ms |
520816 KB |
Output is correct |
38 |
Correct |
409 ms |
518888 KB |
Output is correct |
39 |
Correct |
395 ms |
522732 KB |
Output is correct |
40 |
Correct |
375 ms |
515508 KB |
Output is correct |
41 |
Correct |
379 ms |
520660 KB |
Output is correct |
42 |
Correct |
439 ms |
520724 KB |
Output is correct |
43 |
Correct |
436 ms |
521036 KB |
Output is correct |
44 |
Correct |
439 ms |
520268 KB |
Output is correct |
45 |
Correct |
430 ms |
518880 KB |
Output is correct |
46 |
Correct |
419 ms |
516824 KB |
Output is correct |
47 |
Correct |
393 ms |
514796 KB |
Output is correct |
48 |
Correct |
365 ms |
514252 KB |
Output is correct |
49 |
Correct |
351 ms |
513916 KB |
Output is correct |
50 |
Correct |
396 ms |
518760 KB |
Output is correct |
51 |
Correct |
1 ms |
724 KB |
Output is correct |
52 |
Correct |
5 ms |
4948 KB |
Output is correct |
53 |
Correct |
360 ms |
519516 KB |
Output is correct |
54 |
Correct |
385 ms |
520088 KB |
Output is correct |
55 |
Correct |
409 ms |
514968 KB |
Output is correct |
56 |
Correct |
448 ms |
520020 KB |
Output is correct |
57 |
Correct |
1 ms |
724 KB |
Output is correct |
58 |
Correct |
5 ms |
4948 KB |
Output is correct |
59 |
Correct |
365 ms |
519740 KB |
Output is correct |
60 |
Correct |
460 ms |
520400 KB |
Output is correct |
61 |
Correct |
441 ms |
520392 KB |
Output is correct |
62 |
Correct |
421 ms |
520424 KB |
Output is correct |
63 |
Correct |
401 ms |
517016 KB |
Output is correct |
64 |
Correct |
427 ms |
517920 KB |
Output is correct |
65 |
Correct |
423 ms |
517216 KB |
Output is correct |
66 |
Correct |
391 ms |
520780 KB |
Output is correct |
67 |
Correct |
457 ms |
523272 KB |
Output is correct |
68 |
Correct |
406 ms |
515520 KB |
Output is correct |
69 |
Correct |
410 ms |
520588 KB |
Output is correct |
70 |
Correct |
431 ms |
520672 KB |
Output is correct |
71 |
Correct |
450 ms |
521100 KB |
Output is correct |