#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e5 + 1;
const int LOG = 18;
int L[LOG][N];
int R[LOG][N];
multiset<int> add[N];
multiset<int> del[N];
pii segt[LOG][N * 4 + 512];
void build(int dep, int node, int lef, int rig){
if(lef == rig){
segt[dep][node] = mp(L[dep][lef], R[dep][rig]);
return;
}
int mid = (lef + rig) / 2;
build(dep, node * 2, lef, mid);
build(dep, node * 2 + 1, mid + 1, rig);
segt[dep][node].fi = min(segt[dep][node*2].fi, segt[dep][node*2+1].fi);
segt[dep][node].se = max(segt[dep][node*2].se, segt[dep][node*2+1].se);
}
pii get(int dep, int node, int cl, int cr, int tl, int tr){
if(cr < tl || cl > tr){
return mp((int)1e9,-1);
}
if(cl >= tl && cr <= tr){
return segt[dep][node];
}
int mid = (cl + cr) / 2;
pii A = get(dep, node * 2, cl, mid, tl, tr);
pii B = get(dep, node * 2 + 1, mid + 1, cr, tl, tr);
return mp(min(A.fi, B.fi), max(A.se, B.se));
}
int main(){
fastIO;
//freopen("in.txt","r",stdin);
int n, k;
cin >> n >> k;
int m;
cin >> m;
int seg;
int A, B;
for(int id = 1; id <= m ;id ++ ){
cin >> A >> B;
if(A < B){
seg = min(B, A + k - 1);
add[A].insert(B);
del[seg + 1].insert(B);
}
else{
seg = max(A - k + 1, B);
add[seg].insert(B);
del[A + 1].insert(B);
}
}
multiset<int> pp;
int low;
for(int iq = 1; iq <= n; iq ++ ){
for(auto x : add[iq]){
pp.insert(x);
}
for(auto x : del[iq]){
pp.erase(pp.find(x));
}
L[0][iq] = R[0][iq] = iq;
if(!pp.empty()){
auto it = pp.begin();
L[0][iq] = min(L[0][iq], *it);
it = pp.end();
it -- ;
R[0][iq] = max(R[0][iq], *it);
}
}
pii F;
for(int c = 1; c < LOG; c ++ ){
build(c - 1, 1, 1, n);
for(int iq = 1; iq <= n; iq ++ ){
F = get(c - 1, 1, 1, n, L[c-1][iq], R[c-1][iq]);
L[c][iq] = F.fi;
R[c][iq] = F.se;
}
}
build(LOG - 1, 1, 1, n);
int q;
cin >> q;
int s, t;
int lef, rig;
int dep;
for(int iq = 1; iq <= q; iq ++ ){
cin >> s >> t;
lef = rig = s;
dep = 0;
for(int lg = LOG - 1; lg >= 0 ; lg -- ){
F = get(lg, 1, 1, n, lef, rig);
if(t < F.fi || t > F.se){
lef = F.fi;
rig = F.se;
dep += (1 << lg);
}
}
F = get(0, 1, 1, n, lef, rig);
if(F.fi <= t && t <= F.se){
cout << dep + 1 << "\n";
}
else{
cout << -1 << "\n";
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:72:9: warning: unused variable 'low' [-Wunused-variable]
72 | int low;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10188 KB |
Output is correct |
2 |
Correct |
6 ms |
10188 KB |
Output is correct |
3 |
Correct |
5 ms |
10188 KB |
Output is correct |
4 |
Correct |
6 ms |
10188 KB |
Output is correct |
5 |
Correct |
7 ms |
10188 KB |
Output is correct |
6 |
Correct |
5 ms |
10188 KB |
Output is correct |
7 |
Correct |
7 ms |
10188 KB |
Output is correct |
8 |
Correct |
6 ms |
10188 KB |
Output is correct |
9 |
Correct |
6 ms |
10188 KB |
Output is correct |
10 |
Correct |
5 ms |
9928 KB |
Output is correct |
11 |
Correct |
6 ms |
10188 KB |
Output is correct |
12 |
Correct |
6 ms |
10188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10188 KB |
Output is correct |
2 |
Correct |
6 ms |
10188 KB |
Output is correct |
3 |
Correct |
5 ms |
10188 KB |
Output is correct |
4 |
Correct |
6 ms |
10188 KB |
Output is correct |
5 |
Correct |
7 ms |
10188 KB |
Output is correct |
6 |
Correct |
5 ms |
10188 KB |
Output is correct |
7 |
Correct |
7 ms |
10188 KB |
Output is correct |
8 |
Correct |
6 ms |
10188 KB |
Output is correct |
9 |
Correct |
6 ms |
10188 KB |
Output is correct |
10 |
Correct |
5 ms |
9928 KB |
Output is correct |
11 |
Correct |
6 ms |
10188 KB |
Output is correct |
12 |
Correct |
6 ms |
10188 KB |
Output is correct |
13 |
Correct |
14 ms |
11040 KB |
Output is correct |
14 |
Correct |
13 ms |
10956 KB |
Output is correct |
15 |
Correct |
9 ms |
11008 KB |
Output is correct |
16 |
Correct |
14 ms |
11088 KB |
Output is correct |
17 |
Correct |
16 ms |
10948 KB |
Output is correct |
18 |
Correct |
11 ms |
11124 KB |
Output is correct |
19 |
Correct |
14 ms |
11084 KB |
Output is correct |
20 |
Correct |
10 ms |
11084 KB |
Output is correct |
21 |
Correct |
8 ms |
11084 KB |
Output is correct |
22 |
Correct |
12 ms |
11084 KB |
Output is correct |
23 |
Correct |
17 ms |
11048 KB |
Output is correct |
24 |
Correct |
19 ms |
11060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
452 ms |
68476 KB |
Output is correct |
2 |
Correct |
425 ms |
68240 KB |
Output is correct |
3 |
Correct |
504 ms |
69844 KB |
Output is correct |
4 |
Correct |
401 ms |
67780 KB |
Output is correct |
5 |
Correct |
364 ms |
81844 KB |
Output is correct |
6 |
Correct |
489 ms |
79572 KB |
Output is correct |
7 |
Correct |
226 ms |
84260 KB |
Output is correct |
8 |
Correct |
165 ms |
72280 KB |
Output is correct |
9 |
Correct |
214 ms |
72516 KB |
Output is correct |
10 |
Correct |
519 ms |
79616 KB |
Output is correct |
11 |
Correct |
470 ms |
79696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
636 ms |
71088 KB |
Output is correct |
2 |
Correct |
738 ms |
82052 KB |
Output is correct |
3 |
Correct |
798 ms |
70476 KB |
Output is correct |
4 |
Correct |
400 ms |
84440 KB |
Output is correct |
5 |
Correct |
451 ms |
84424 KB |
Output is correct |
6 |
Correct |
487 ms |
84276 KB |
Output is correct |
7 |
Correct |
747 ms |
79828 KB |
Output is correct |
8 |
Correct |
743 ms |
79764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
770 ms |
82256 KB |
Output is correct |
2 |
Correct |
763 ms |
70492 KB |
Output is correct |
3 |
Correct |
751 ms |
65796 KB |
Output is correct |
4 |
Correct |
741 ms |
62856 KB |
Output is correct |
5 |
Correct |
575 ms |
61492 KB |
Output is correct |
6 |
Correct |
651 ms |
61112 KB |
Output is correct |
7 |
Correct |
461 ms |
74992 KB |
Output is correct |
8 |
Correct |
7 ms |
10188 KB |
Output is correct |
9 |
Correct |
16 ms |
11084 KB |
Output is correct |
10 |
Correct |
546 ms |
82800 KB |
Output is correct |
11 |
Correct |
617 ms |
84548 KB |
Output is correct |
12 |
Correct |
686 ms |
82700 KB |
Output is correct |
13 |
Correct |
682 ms |
84292 KB |
Output is correct |
14 |
Correct |
6 ms |
10188 KB |
Output is correct |
15 |
Correct |
17 ms |
10956 KB |
Output is correct |
16 |
Correct |
567 ms |
79508 KB |
Output is correct |
17 |
Correct |
850 ms |
79824 KB |
Output is correct |
18 |
Correct |
853 ms |
79852 KB |
Output is correct |
19 |
Correct |
823 ms |
79784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10188 KB |
Output is correct |
2 |
Correct |
6 ms |
10188 KB |
Output is correct |
3 |
Correct |
5 ms |
10188 KB |
Output is correct |
4 |
Correct |
6 ms |
10188 KB |
Output is correct |
5 |
Correct |
7 ms |
10188 KB |
Output is correct |
6 |
Correct |
5 ms |
10188 KB |
Output is correct |
7 |
Correct |
7 ms |
10188 KB |
Output is correct |
8 |
Correct |
6 ms |
10188 KB |
Output is correct |
9 |
Correct |
6 ms |
10188 KB |
Output is correct |
10 |
Correct |
5 ms |
9928 KB |
Output is correct |
11 |
Correct |
6 ms |
10188 KB |
Output is correct |
12 |
Correct |
6 ms |
10188 KB |
Output is correct |
13 |
Correct |
14 ms |
11040 KB |
Output is correct |
14 |
Correct |
13 ms |
10956 KB |
Output is correct |
15 |
Correct |
9 ms |
11008 KB |
Output is correct |
16 |
Correct |
14 ms |
11088 KB |
Output is correct |
17 |
Correct |
16 ms |
10948 KB |
Output is correct |
18 |
Correct |
11 ms |
11124 KB |
Output is correct |
19 |
Correct |
14 ms |
11084 KB |
Output is correct |
20 |
Correct |
10 ms |
11084 KB |
Output is correct |
21 |
Correct |
8 ms |
11084 KB |
Output is correct |
22 |
Correct |
12 ms |
11084 KB |
Output is correct |
23 |
Correct |
17 ms |
11048 KB |
Output is correct |
24 |
Correct |
19 ms |
11060 KB |
Output is correct |
25 |
Correct |
452 ms |
68476 KB |
Output is correct |
26 |
Correct |
425 ms |
68240 KB |
Output is correct |
27 |
Correct |
504 ms |
69844 KB |
Output is correct |
28 |
Correct |
401 ms |
67780 KB |
Output is correct |
29 |
Correct |
364 ms |
81844 KB |
Output is correct |
30 |
Correct |
489 ms |
79572 KB |
Output is correct |
31 |
Correct |
226 ms |
84260 KB |
Output is correct |
32 |
Correct |
165 ms |
72280 KB |
Output is correct |
33 |
Correct |
214 ms |
72516 KB |
Output is correct |
34 |
Correct |
519 ms |
79616 KB |
Output is correct |
35 |
Correct |
470 ms |
79696 KB |
Output is correct |
36 |
Correct |
636 ms |
71088 KB |
Output is correct |
37 |
Correct |
738 ms |
82052 KB |
Output is correct |
38 |
Correct |
798 ms |
70476 KB |
Output is correct |
39 |
Correct |
400 ms |
84440 KB |
Output is correct |
40 |
Correct |
451 ms |
84424 KB |
Output is correct |
41 |
Correct |
487 ms |
84276 KB |
Output is correct |
42 |
Correct |
747 ms |
79828 KB |
Output is correct |
43 |
Correct |
743 ms |
79764 KB |
Output is correct |
44 |
Correct |
770 ms |
82256 KB |
Output is correct |
45 |
Correct |
763 ms |
70492 KB |
Output is correct |
46 |
Correct |
751 ms |
65796 KB |
Output is correct |
47 |
Correct |
741 ms |
62856 KB |
Output is correct |
48 |
Correct |
575 ms |
61492 KB |
Output is correct |
49 |
Correct |
651 ms |
61112 KB |
Output is correct |
50 |
Correct |
461 ms |
74992 KB |
Output is correct |
51 |
Correct |
7 ms |
10188 KB |
Output is correct |
52 |
Correct |
16 ms |
11084 KB |
Output is correct |
53 |
Correct |
546 ms |
82800 KB |
Output is correct |
54 |
Correct |
617 ms |
84548 KB |
Output is correct |
55 |
Correct |
686 ms |
82700 KB |
Output is correct |
56 |
Correct |
682 ms |
84292 KB |
Output is correct |
57 |
Correct |
6 ms |
10188 KB |
Output is correct |
58 |
Correct |
17 ms |
10956 KB |
Output is correct |
59 |
Correct |
567 ms |
79508 KB |
Output is correct |
60 |
Correct |
850 ms |
79824 KB |
Output is correct |
61 |
Correct |
853 ms |
79852 KB |
Output is correct |
62 |
Correct |
823 ms |
79784 KB |
Output is correct |
63 |
Correct |
694 ms |
67708 KB |
Output is correct |
64 |
Correct |
790 ms |
69468 KB |
Output is correct |
65 |
Correct |
705 ms |
68040 KB |
Output is correct |
66 |
Correct |
361 ms |
82048 KB |
Output is correct |
67 |
Correct |
729 ms |
79904 KB |
Output is correct |
68 |
Correct |
651 ms |
80368 KB |
Output is correct |
69 |
Correct |
463 ms |
84180 KB |
Output is correct |
70 |
Correct |
741 ms |
79784 KB |
Output is correct |
71 |
Correct |
809 ms |
79812 KB |
Output is correct |