Submission #834148

#	Time	Username	Problem	Language	Result	Execution time	Memory
834148		mosiashvililuka	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	684 ms	107148 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);
}*/
void read(int q, int w, int 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);
}
void UPD(int q, int zl, int zr){
    q=za+q-1;
    segMN[JJ][q]=zl;segMX[JJ][q]=zr;
    q/=2;
    while(q){
        segMX[JJ][q]=max(segMX[JJ][q*2],segMX[JJ][q*2+1]);
        segMN[JJ][q]=min(segMN[JJ][q*2],segMN[JJ][q*2+1]);
        q>>=1;
    }
}
vector <int> MN[100009],MX[100009];
multiset <int> sMN,sMX;
multiset <int>::iterator it;
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);
            MX[l].push_back(zr);
            MX[r+1].push_back(-zr);
        }else{
            swap(c,d);
            l=max(d-K+1,c);r=d;JJ=0;
            zl=c;zr=0;
            //upd(1,za,1);
            MN[l].push_back(zl);
            MN[r+1].push_back(-zl);
        }
    }

    for(i=1; i<=a; i++){
        for(auto x:MN[i]){
            if(x>=0){
                sMN.insert(x);
            }else{
                sMN.erase(sMN.find(-x));
            }

        }

        for(auto x:MX[i]){
            if(x>=0){
                sMX.insert(x);
            }else{
                sMX.erase(sMX.find(-x));
            }

        }

        lf[0][i]=rg[0][i]=i;
        if(sMN.size()){
            it=sMN.begin();
            lf[0][i]=(*it);
        }
        if(sMX.size()){
            it=sMX.end();
            it--;
            rg[0][i]=(*it);
        }
    }

    for(i=1; i<=a; i++){
        JJ=0;
        l=i;r=i;
        zl=lf[0][i];zr=rg[0][i];
        //cout<<i<<" "<<zl<<" "<<zr<<"\n";
        UPD(i,zl,zr);
    }


    /*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);
            UPD(i,zl,zr);
        }
    }


    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: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13