이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |