Submission #834091

#	Time	Username	Problem	Language	Result	Execution time	Memory
834091		mosiashvililuka	Railway Trip 2 (JOI22_ho_t4)	C++14	27 / 100	2059 ms	89724 KiB

Main

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13