제출 #834076

#제출 시각아이디문제언어결과실행 시간메모리
834076mosiashvililukaRailway Trip 2 (JOI22_ho_t4)C++14
27 / 100
2066 ms88692 KiB
#include<bits/stdc++.h> using namespace std; int zl,zr; 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; 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=16; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...