#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,zx,xc,K,tes,t,segMN[19][400009],segMN2[19][400009],segMX[19][400009],segMX2[19][400009],l,r,z,za,lf[19][400009],rg[19][400009],L,R,pas,ANS;
int JJ;
void pushdownMX(int q, int w, int rr){
if(q!=w){
segMX2[JJ][rr*2]=max(segMX2[JJ][rr*2],segMX2[JJ][rr]);
segMX2[JJ][rr*2+1]=max(segMX2[JJ][rr*2+1],segMX2[JJ][rr]);
}
segMX[JJ][rr]=max(segMX[JJ][rr],segMX2[JJ][rr]);
segMX2[JJ][rr]=0;
}
void updMX(int q, int w, int rr){
pushdownMX(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
segMX2[JJ][rr]=z;
pushdownMX(q,w,rr);
return;
}
updMX(q,(q+w)/2,rr*2);
updMX((q+w)/2+1,w,rr*2+1);
segMX[JJ][rr]=max(segMX[JJ][rr*2],segMX[JJ][rr*2+1]);
}
//
void pushdownMN(int q, int w, int rr){
if(q!=w){
segMN2[JJ][rr*2]=min(segMN2[JJ][rr*2],segMN2[JJ][rr]);
segMN2[JJ][rr*2+1]=min(segMN2[JJ][rr*2+1],segMN2[JJ][rr]);
}
segMN[JJ][rr]=min(segMN[JJ][rr],segMN2[JJ][rr]);
segMN2[JJ][rr]=a+2;
}
void updMN(int q, int w, int rr){
pushdownMN(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
segMN2[JJ][rr]=z;
pushdownMN(q,w,rr);
return;
}
updMN(q,(q+w)/2,rr*2);
updMN((q+w)/2+1,w,rr*2+1);
segMN[JJ][rr]=min(segMN[JJ][rr*2],segMN[JJ][rr*2+1]);
}
//
void readMX(int q, int w, int rr){
pushdownMX(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,segMX[JJ][rr]);
return;
}
readMX(q,(q+w)/2,rr*2);
readMX((q+w)/2+1,w,rr*2+1);
}
void readMN(int q, int w, int rr){
pushdownMN(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=min(z,segMN[JJ][rr]);
return;
}
readMN(q,(q+w)/2,rr*2);
readMN((q+w)/2+1,w,rr*2+1);
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>K;
cin>>b;
za=1;
while(za<a) za*=2;
for(j=0; j<=18; j++){
for(i=0; i<=za*2; i++){
segMN[j][i]=a+2;
segMX[j][i]=0;
segMN2[j][i]=a+2;
segMX2[j][i]=0;
}
}
for(ii=1; ii<=b; ii++){
cin>>c>>d;
if(c<=d){
l=c;r=min(d,c+K-1);z=d;JJ=0;
updMX(1,za,1);
}else{
swap(c,d);
l=max(d-K+1,c);r=d;z=c;JJ=0;
updMN(1,za,1);
}
}
for(i=1; i<=a; i++){
//lf[0][i]=rg[0][i]=i;
l=i;r=i;z=a+2;
readMN(1,za,1);
c=min(z,i);
l=i;r=i;z=0;
readMX(1,za,1);
d=max(z,i);
lf[0][i]=c;
rg[0][i]=d;
}
for(j=0; j<17; j++){
for(i=1; i<=a; i++){
l=lf[j][i];r=rg[j][i];z=a+2;JJ=j;
readMN(1,za,1);
c=min(z,lf[j][i]);
l=lf[j][i];r=rg[j][i];z=0;JJ=j;
readMX(1,za,1);
d=max(z,rg[j][i]);
/*zx=c;xc=d;
l=c;r=d;z=a+2;JJ=j;
readMN(1,za,1);
zx=min(zx,z);
l=c;r=d;z=0;JJ=j;
readMX(1,za,1);
xc=max(xc,z);*/
//c=zx;d=xc;
lf[j+1][i]=c;rg[j+1][i]=d;
l=i;r=i;z=d;JJ=j+1;
updMX(1,za,1);
l=i;r=i;z=c;JJ=j+1;
updMN(1,za,1);
}
}
cin>>tes;
for(t=1; t<=tes; t++){
cin>>c>>d;
L=c;R=c;
ANS=b+1;pas=0;
for(j=17; j>=0; j--){
zx=L;xc=R;
l=L;r=R;z=0;JJ=j;
readMX(1,za,1);
xc=max(xc,z);
l=L;r=R;z=a+2;JJ=j;
readMN(1,za,1);
zx=min(zx,z);
//cout<<j<<": "<<L<<" "<<R<<" "<<zx<<" "<<xc<<"\n";
if(zx<=d&&d<=xc){
ANS=min(ANS,pas+(1<<j));
}else{
pas+=(1<<j);
L=min(L,zx);
R=max(R,xc);
}
}
if(ANS==b+1) cout<<"-1\n"; else cout<<ANS<<"\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
1364 KB |
Output is correct |
2 |
Correct |
5 ms |
1364 KB |
Output is correct |
3 |
Correct |
4 ms |
1364 KB |
Output is correct |
4 |
Correct |
6 ms |
1364 KB |
Output is correct |
5 |
Correct |
5 ms |
1356 KB |
Output is correct |
6 |
Correct |
4 ms |
1364 KB |
Output is correct |
7 |
Correct |
4 ms |
1364 KB |
Output is correct |
8 |
Correct |
4 ms |
1356 KB |
Output is correct |
9 |
Correct |
4 ms |
1364 KB |
Output is correct |
10 |
Correct |
1 ms |
1108 KB |
Output is correct |
11 |
Correct |
4 ms |
1364 KB |
Output is correct |
12 |
Correct |
5 ms |
1364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
1364 KB |
Output is correct |
2 |
Correct |
5 ms |
1364 KB |
Output is correct |
3 |
Correct |
4 ms |
1364 KB |
Output is correct |
4 |
Correct |
6 ms |
1364 KB |
Output is correct |
5 |
Correct |
5 ms |
1356 KB |
Output is correct |
6 |
Correct |
4 ms |
1364 KB |
Output is correct |
7 |
Correct |
4 ms |
1364 KB |
Output is correct |
8 |
Correct |
4 ms |
1356 KB |
Output is correct |
9 |
Correct |
4 ms |
1364 KB |
Output is correct |
10 |
Correct |
1 ms |
1108 KB |
Output is correct |
11 |
Correct |
4 ms |
1364 KB |
Output is correct |
12 |
Correct |
5 ms |
1364 KB |
Output is correct |
13 |
Correct |
37 ms |
2528 KB |
Output is correct |
14 |
Correct |
36 ms |
2624 KB |
Output is correct |
15 |
Correct |
25 ms |
2568 KB |
Output is correct |
16 |
Correct |
32 ms |
2516 KB |
Output is correct |
17 |
Correct |
36 ms |
2624 KB |
Output is correct |
18 |
Correct |
28 ms |
2596 KB |
Output is correct |
19 |
Correct |
34 ms |
2552 KB |
Output is correct |
20 |
Correct |
27 ms |
2636 KB |
Output is correct |
21 |
Correct |
19 ms |
2580 KB |
Output is correct |
22 |
Correct |
36 ms |
2648 KB |
Output is correct |
23 |
Correct |
31 ms |
2628 KB |
Output is correct |
24 |
Correct |
36 ms |
2516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2060 ms |
93596 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2069 ms |
94508 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2037 ms |
95548 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
1364 KB |
Output is correct |
2 |
Correct |
5 ms |
1364 KB |
Output is correct |
3 |
Correct |
4 ms |
1364 KB |
Output is correct |
4 |
Correct |
6 ms |
1364 KB |
Output is correct |
5 |
Correct |
5 ms |
1356 KB |
Output is correct |
6 |
Correct |
4 ms |
1364 KB |
Output is correct |
7 |
Correct |
4 ms |
1364 KB |
Output is correct |
8 |
Correct |
4 ms |
1356 KB |
Output is correct |
9 |
Correct |
4 ms |
1364 KB |
Output is correct |
10 |
Correct |
1 ms |
1108 KB |
Output is correct |
11 |
Correct |
4 ms |
1364 KB |
Output is correct |
12 |
Correct |
5 ms |
1364 KB |
Output is correct |
13 |
Correct |
37 ms |
2528 KB |
Output is correct |
14 |
Correct |
36 ms |
2624 KB |
Output is correct |
15 |
Correct |
25 ms |
2568 KB |
Output is correct |
16 |
Correct |
32 ms |
2516 KB |
Output is correct |
17 |
Correct |
36 ms |
2624 KB |
Output is correct |
18 |
Correct |
28 ms |
2596 KB |
Output is correct |
19 |
Correct |
34 ms |
2552 KB |
Output is correct |
20 |
Correct |
27 ms |
2636 KB |
Output is correct |
21 |
Correct |
19 ms |
2580 KB |
Output is correct |
22 |
Correct |
36 ms |
2648 KB |
Output is correct |
23 |
Correct |
31 ms |
2628 KB |
Output is correct |
24 |
Correct |
36 ms |
2516 KB |
Output is correct |
25 |
Execution timed out |
2060 ms |
93596 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |