이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
int zl,zr;
int MDE;
int a,b,c,d,e,i,j,ii,zx,xc,K,tes,t,segMN[18][400009],segMN2[18][400009],segMX[18][400009],segMX2[18][400009],l,r,za,lf[18][400009],rg[18][400009],L,R,pas,ANS;
int JJ;
void pushdown(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]);
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]);
}
segMX[JJ][rr]=max(segMX[JJ][rr],segMX2[JJ][rr]);
segMX2[JJ][rr]=0;
segMN[JJ][rr]=min(segMN[JJ][rr],segMN2[JJ][rr]);
segMN2[JJ][rr]=a+2;
}
void upd(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
segMX2[JJ][rr]=zr;
segMN2[JJ][rr]=zl;
pushdown(q,w,rr);
return;
}
upd(q,((q+w)>>1),rr*2);
upd(((q+w)>>1)+1,w,rr*2+1);
segMX[JJ][rr]=max(segMX[JJ][rr*2],segMX[JJ][rr*2+1]);
segMN[JJ][rr]=min(segMN[JJ][rr*2],segMN[JJ][rr*2+1]);
}
void read(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
zr=max(zr,segMX[JJ][rr]);
zl=min(zl,segMN[JJ][rr]);
return;
}
read(q,((q+w)>>1),rr*2);
read(((q+w)>>1)+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<=17; 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);JJ=0;
zr=d;zl=a+2;
upd(1,za,1);
}else{
swap(c,d);
l=max(d-K+1,c);r=d;JJ=0;
zl=c;zr=0;
upd(1,za,1);
}
}
for(i=1; i<=a; i++){
//lf[0][i]=rg[0][i]=i;
l=i;r=i;zl=a+2;zr=0;JJ=0;
read(1,za,1);
c=min(zl,i);
d=max(zr,i);
lf[0][i]=c;
rg[0][i]=d;
}
for(j=0; j<16; j++){
for(i=1; i<=a; i++){
l=lf[j][i];r=rg[j][i];JJ=j;
zl=a+2;zr=0;
read(1,za,1);
c=min(zl,lf[j][i]);
d=max(zr,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;
if(c>=lf[j][i]&&d<=rg[j][i]){
;
}else{
MDE=max(MDE,j+1);
}
l=i;r=i;JJ=j+1;
zr=d;zl=c;
upd(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=MDE; j>=0; j--){
zx=L;xc=R;
l=L;r=R;JJ=j;
zr=0;zl=a+2;
read(1,za,1);
xc=max(xc,zr);
zx=min(zx,zl);
//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... |