#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr int M = 2e5;
constexpr int K = 20;
constexpr int base = (1<<17);
pair<int,int> tree[2*base+9][K];
pair<int,int> lazy[2*base+9];
void daj(int x, int k){
tree[2*x][k].first = min(tree[2*x][k].first,lazy[x].first);
tree[2*x][k].second = max(tree[2*x][k].second,lazy[x].second);
lazy[2*x].first = min(lazy[2*x].first,lazy[x].first);
lazy[2*x].second = max(lazy[2*x].second,lazy[x].second);
tree[2*x+1][k].first = min(tree[2*x+1][k].first,lazy[x].first);
tree[2*x+1][k].second = max(tree[2*x+1][k].second,lazy[x].second);
lazy[2*x+1].first = min(lazy[2*x+1].first,lazy[x].first);
lazy[2*x+1].second = max(lazy[2*x+1].second,lazy[x].second);
tree[x][k].first = min(tree[2*x][k].first,tree[2*x+1][k].first);
tree[x][k].second = max(tree[2*x][k].second,tree[2*x+1][k].second);
lazy[x] = {1e9,-1e9};
}
void sed(int x, int l, int a, int b, int p, int k, pair<int,int> val){
if (p<=a && b<=k){
tree[x][l].first = min(tree[x][l].first,val.first);
tree[x][l].second = max(tree[x][l].second,val.second);
lazy[x].first = min(lazy[x].first,val.first);
lazy[x].second = max(lazy[x].second,val.second);
return;
}
if (b<p || a>k) return;
daj(x,l);
int mid=(a+b)/2;
sed(2*x,l,a,mid,p,k,val);
sed(2*x+1,l,mid+1,b,p,k,val);
tree[x][l].first = min(tree[2*x][l].first,tree[2*x+1][l].first);
tree[x][l].second = max(tree[2*x][l].second,tree[2*x+1][l].second);
}
void sed2(int x, int k, pair<int,int> val){
x+=base-1;
tree[x][k] = val;
while(x>1){
x /= 2;
tree[x][k].first = min(tree[2*x][k].first, tree[2*x+1][k].first);
tree[x][k].second = max(tree[2*x][k].second, tree[2*x+1][k].second);
}
}
pair<int,int> query(int x, int l, int a, int b, int p, int k){
if (p<=a && b<=k) return tree[x][l];
if (b<p || a>k) return {1e9,-1e9};
int mid=(a+b)/2;
if (l==0) daj(x,l);
pair<int,int> j = query(2*x,l,a,mid,p,k);
pair<int,int> d = query(2*x+1,l,mid+1,b,p,k);
tree[x][l].first = min(tree[2*x][l].first,tree[2*x+1][l].first);
tree[x][l].second = max(tree[2*x][l].second,tree[2*x+1][l].second);
return {min(j.first,d.first),max(j.second,d.second)};
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,zas,m,a,b,q;
cin >> n >> zas;
cin >> m;
for (int k=0;k<K;k++){
for (int x=0;x<=2*base;x++) tree[x][k] = {1e9,-1e9};
}
for (int x=0;x<=2*base;x++) lazy[x] = {1e9,-1e9};
for (int x=1;x<=n;x++) tree[x+base-1][0] = {x,x};
for (int x=base-1;x>=1;x--){
tree[x][0].first = min(tree[2*x][0].first,tree[2*x+1][0].second);
tree[x][0].second = max(tree[2*x][0].first,tree[2*x+1][0].second);
}
for (int x=0;x<m;x++){
cin >> a >> b;
if (a<b) sed(1,0,1,base,a,min(a+zas-1,b),{1e9,b});
if (a>b) sed(1,0,1,base,max(a-zas+1,b),a,{b,-1e9});
}
for (int x=1;x<base;x++) daj(x,0);
for (int k=1;k<K;k++){
for (int x=1;x<=n;x++){
sed2(x,k,query(1,k-1,1,base,tree[x+base-1][k-1].first,tree[x+base-1][k-1].second));
}
}
/*for (int k=0;k<K;k++){
for (int x=1;x<=n;x++){
pair<int,int> xd = query(1,k,1,base,x,x);
cout << x << ' ' << (1<<k) << ' ' << xd.first << ' ' << xd.second << '\n';
}
}*/
cin >> q;
while(q--){
cin >> a >> b;
int odp=0;
pair<int,int> range = {a,a};
for (int k=K-1;k>=0;k--){
pair<int,int> temp = query(1,k,1,base,range.first,range.second);
if (!(temp.first <= b && b <= temp.second)){
odp += (1<<k);
range =temp;
}
}
if (odp+1 == (1<<K)) cout << "-1\n";
else cout << odp+1 << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
43516 KB |
Output is correct |
2 |
Correct |
50 ms |
43376 KB |
Output is correct |
3 |
Correct |
47 ms |
43528 KB |
Output is correct |
4 |
Correct |
51 ms |
43476 KB |
Output is correct |
5 |
Correct |
54 ms |
43356 KB |
Output is correct |
6 |
Correct |
45 ms |
43372 KB |
Output is correct |
7 |
Correct |
50 ms |
43528 KB |
Output is correct |
8 |
Correct |
49 ms |
43368 KB |
Output is correct |
9 |
Correct |
47 ms |
43536 KB |
Output is correct |
10 |
Correct |
52 ms |
43528 KB |
Output is correct |
11 |
Correct |
49 ms |
43372 KB |
Output is correct |
12 |
Correct |
43 ms |
43356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
43516 KB |
Output is correct |
2 |
Correct |
50 ms |
43376 KB |
Output is correct |
3 |
Correct |
47 ms |
43528 KB |
Output is correct |
4 |
Correct |
51 ms |
43476 KB |
Output is correct |
5 |
Correct |
54 ms |
43356 KB |
Output is correct |
6 |
Correct |
45 ms |
43372 KB |
Output is correct |
7 |
Correct |
50 ms |
43528 KB |
Output is correct |
8 |
Correct |
49 ms |
43368 KB |
Output is correct |
9 |
Correct |
47 ms |
43536 KB |
Output is correct |
10 |
Correct |
52 ms |
43528 KB |
Output is correct |
11 |
Correct |
49 ms |
43372 KB |
Output is correct |
12 |
Correct |
43 ms |
43356 KB |
Output is correct |
13 |
Correct |
69 ms |
43564 KB |
Output is correct |
14 |
Correct |
61 ms |
43372 KB |
Output is correct |
15 |
Correct |
52 ms |
43368 KB |
Output is correct |
16 |
Correct |
76 ms |
43368 KB |
Output is correct |
17 |
Correct |
72 ms |
43356 KB |
Output is correct |
18 |
Correct |
60 ms |
43540 KB |
Output is correct |
19 |
Correct |
64 ms |
43364 KB |
Output is correct |
20 |
Correct |
62 ms |
43364 KB |
Output is correct |
21 |
Correct |
66 ms |
43356 KB |
Output is correct |
22 |
Correct |
61 ms |
43352 KB |
Output is correct |
23 |
Correct |
66 ms |
43464 KB |
Output is correct |
24 |
Correct |
62 ms |
43380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
912 ms |
43528 KB |
Output is correct |
2 |
Correct |
877 ms |
44436 KB |
Output is correct |
3 |
Correct |
924 ms |
44636 KB |
Output is correct |
4 |
Correct |
823 ms |
44384 KB |
Output is correct |
5 |
Correct |
834 ms |
45832 KB |
Output is correct |
6 |
Correct |
877 ms |
45832 KB |
Output is correct |
7 |
Correct |
577 ms |
45560 KB |
Output is correct |
8 |
Correct |
613 ms |
44660 KB |
Output is correct |
9 |
Correct |
561 ms |
44664 KB |
Output is correct |
10 |
Correct |
930 ms |
45828 KB |
Output is correct |
11 |
Correct |
807 ms |
45828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1000 ms |
43528 KB |
Output is correct |
2 |
Correct |
1088 ms |
43528 KB |
Output is correct |
3 |
Correct |
1268 ms |
43904 KB |
Output is correct |
4 |
Correct |
772 ms |
43632 KB |
Output is correct |
5 |
Correct |
871 ms |
43600 KB |
Output is correct |
6 |
Correct |
852 ms |
43612 KB |
Output is correct |
7 |
Correct |
1091 ms |
43528 KB |
Output is correct |
8 |
Correct |
997 ms |
43544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1302 ms |
43952 KB |
Output is correct |
2 |
Correct |
1184 ms |
43780 KB |
Output is correct |
3 |
Correct |
1074 ms |
43788 KB |
Output is correct |
4 |
Correct |
1137 ms |
43984 KB |
Output is correct |
5 |
Correct |
912 ms |
43864 KB |
Output is correct |
6 |
Correct |
1071 ms |
43524 KB |
Output is correct |
7 |
Correct |
1037 ms |
43624 KB |
Output is correct |
8 |
Correct |
43 ms |
43352 KB |
Output is correct |
9 |
Correct |
67 ms |
43352 KB |
Output is correct |
10 |
Correct |
944 ms |
43532 KB |
Output is correct |
11 |
Correct |
1121 ms |
43628 KB |
Output is correct |
12 |
Correct |
1158 ms |
43688 KB |
Output is correct |
13 |
Correct |
1137 ms |
43600 KB |
Output is correct |
14 |
Correct |
44 ms |
43352 KB |
Output is correct |
15 |
Correct |
60 ms |
43356 KB |
Output is correct |
16 |
Correct |
909 ms |
45904 KB |
Output is correct |
17 |
Correct |
1195 ms |
46580 KB |
Output is correct |
18 |
Correct |
1240 ms |
46796 KB |
Output is correct |
19 |
Correct |
1175 ms |
46504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
43516 KB |
Output is correct |
2 |
Correct |
50 ms |
43376 KB |
Output is correct |
3 |
Correct |
47 ms |
43528 KB |
Output is correct |
4 |
Correct |
51 ms |
43476 KB |
Output is correct |
5 |
Correct |
54 ms |
43356 KB |
Output is correct |
6 |
Correct |
45 ms |
43372 KB |
Output is correct |
7 |
Correct |
50 ms |
43528 KB |
Output is correct |
8 |
Correct |
49 ms |
43368 KB |
Output is correct |
9 |
Correct |
47 ms |
43536 KB |
Output is correct |
10 |
Correct |
52 ms |
43528 KB |
Output is correct |
11 |
Correct |
49 ms |
43372 KB |
Output is correct |
12 |
Correct |
43 ms |
43356 KB |
Output is correct |
13 |
Correct |
69 ms |
43564 KB |
Output is correct |
14 |
Correct |
61 ms |
43372 KB |
Output is correct |
15 |
Correct |
52 ms |
43368 KB |
Output is correct |
16 |
Correct |
76 ms |
43368 KB |
Output is correct |
17 |
Correct |
72 ms |
43356 KB |
Output is correct |
18 |
Correct |
60 ms |
43540 KB |
Output is correct |
19 |
Correct |
64 ms |
43364 KB |
Output is correct |
20 |
Correct |
62 ms |
43364 KB |
Output is correct |
21 |
Correct |
66 ms |
43356 KB |
Output is correct |
22 |
Correct |
61 ms |
43352 KB |
Output is correct |
23 |
Correct |
66 ms |
43464 KB |
Output is correct |
24 |
Correct |
62 ms |
43380 KB |
Output is correct |
25 |
Correct |
912 ms |
43528 KB |
Output is correct |
26 |
Correct |
877 ms |
44436 KB |
Output is correct |
27 |
Correct |
924 ms |
44636 KB |
Output is correct |
28 |
Correct |
823 ms |
44384 KB |
Output is correct |
29 |
Correct |
834 ms |
45832 KB |
Output is correct |
30 |
Correct |
877 ms |
45832 KB |
Output is correct |
31 |
Correct |
577 ms |
45560 KB |
Output is correct |
32 |
Correct |
613 ms |
44660 KB |
Output is correct |
33 |
Correct |
561 ms |
44664 KB |
Output is correct |
34 |
Correct |
930 ms |
45828 KB |
Output is correct |
35 |
Correct |
807 ms |
45828 KB |
Output is correct |
36 |
Correct |
1000 ms |
43528 KB |
Output is correct |
37 |
Correct |
1088 ms |
43528 KB |
Output is correct |
38 |
Correct |
1268 ms |
43904 KB |
Output is correct |
39 |
Correct |
772 ms |
43632 KB |
Output is correct |
40 |
Correct |
871 ms |
43600 KB |
Output is correct |
41 |
Correct |
852 ms |
43612 KB |
Output is correct |
42 |
Correct |
1091 ms |
43528 KB |
Output is correct |
43 |
Correct |
997 ms |
43544 KB |
Output is correct |
44 |
Correct |
1302 ms |
43952 KB |
Output is correct |
45 |
Correct |
1184 ms |
43780 KB |
Output is correct |
46 |
Correct |
1074 ms |
43788 KB |
Output is correct |
47 |
Correct |
1137 ms |
43984 KB |
Output is correct |
48 |
Correct |
912 ms |
43864 KB |
Output is correct |
49 |
Correct |
1071 ms |
43524 KB |
Output is correct |
50 |
Correct |
1037 ms |
43624 KB |
Output is correct |
51 |
Correct |
43 ms |
43352 KB |
Output is correct |
52 |
Correct |
67 ms |
43352 KB |
Output is correct |
53 |
Correct |
944 ms |
43532 KB |
Output is correct |
54 |
Correct |
1121 ms |
43628 KB |
Output is correct |
55 |
Correct |
1158 ms |
43688 KB |
Output is correct |
56 |
Correct |
1137 ms |
43600 KB |
Output is correct |
57 |
Correct |
44 ms |
43352 KB |
Output is correct |
58 |
Correct |
60 ms |
43356 KB |
Output is correct |
59 |
Correct |
909 ms |
45904 KB |
Output is correct |
60 |
Correct |
1195 ms |
46580 KB |
Output is correct |
61 |
Correct |
1240 ms |
46796 KB |
Output is correct |
62 |
Correct |
1175 ms |
46504 KB |
Output is correct |
63 |
Correct |
1117 ms |
45044 KB |
Output is correct |
64 |
Correct |
1291 ms |
45808 KB |
Output is correct |
65 |
Correct |
1120 ms |
45136 KB |
Output is correct |
66 |
Correct |
1033 ms |
46548 KB |
Output is correct |
67 |
Correct |
1130 ms |
46712 KB |
Output is correct |
68 |
Correct |
940 ms |
46420 KB |
Output is correct |
69 |
Correct |
966 ms |
46584 KB |
Output is correct |
70 |
Correct |
1148 ms |
46324 KB |
Output is correct |
71 |
Correct |
1203 ms |
46580 KB |
Output is correct |