Submission #834027

#	Time	Username	Problem	Language	Result	Execution time	Memory
834027		mosiashvililuka	Railway Trip 2 (JOI22_ho_t4)	C++14	16 / 100	2069 ms	95548 KiB

Main

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

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