oj.uz

Submission #834091

# Submission time Handle Problem Language Result Execution time Memory
834091 2023-08-22T10:42:07 Z mosiashvililuka Railway Trip 2 (JOI22_ho_t4) C++14
27 / 100
 2000 ms 89724 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 3 ms 1364 KB Output is correct
5 Correct 3 ms 1364 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1360 KB Output is correct
8 Correct 3 ms 1360 KB Output is correct
9 Correct 3 ms 1364 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 3 ms 1364 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 3 ms 1364 KB Output is correct
5 Correct 3 ms 1364 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1360 KB Output is correct
8 Correct 3 ms 1360 KB Output is correct
9 Correct 3 ms 1364 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 3 ms 1364 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 28 ms 2400 KB Output is correct
14 Correct 25 ms 2528 KB Output is correct
15 Correct 18 ms 2488 KB Output is correct
16 Correct 19 ms 2408 KB Output is correct
17 Correct 26 ms 2516 KB Output is correct
18 Correct 15 ms 2448 KB Output is correct
19 Correct 21 ms 2416 KB Output is correct
20 Correct 17 ms 2524 KB Output is correct
21 Correct 18 ms 2392 KB Output is correct
22 Correct 22 ms 2520 KB Output is correct
23 Correct 26 ms 2440 KB Output is correct
24 Correct 26 ms 2520 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1589 ms 88380 KB Output is correct
2 Correct 1588 ms 88248 KB Output is correct
3 Correct 1715 ms 88300 KB Output is correct
4 Correct 1520 ms 88332 KB Output is correct
5 Correct 1436 ms 88220 KB Output is correct
6 Correct 1596 ms 88240 KB Output is correct
7 Correct 1246 ms 88240 KB Output is correct
8 Correct 1274 ms 88544 KB Output is correct
9 Correct 1290 ms 88708 KB Output is correct
10 Correct 1646 ms 88704 KB Output is correct
11 Correct 1546 ms 88628 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 88496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1809 ms 88712 KB Output is correct
2 Execution timed out 2059 ms 89724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 3 ms 1364 KB Output is correct
5 Correct 3 ms 1364 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 3 ms 1360 KB Output is correct
8 Correct 3 ms 1360 KB Output is correct
9 Correct 3 ms 1364 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 3 ms 1364 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 28 ms 2400 KB Output is correct
14 Correct 25 ms 2528 KB Output is correct
15 Correct 18 ms 2488 KB Output is correct
16 Correct 19 ms 2408 KB Output is correct
17 Correct 26 ms 2516 KB Output is correct
18 Correct 15 ms 2448 KB Output is correct
19 Correct 21 ms 2416 KB Output is correct
20 Correct 17 ms 2524 KB Output is correct
21 Correct 18 ms 2392 KB Output is correct
22 Correct 22 ms 2520 KB Output is correct
23 Correct 26 ms 2440 KB Output is correct
24 Correct 26 ms 2520 KB Output is correct
25 Correct 1589 ms 88380 KB Output is correct
26 Correct 1588 ms 88248 KB Output is correct
27 Correct 1715 ms 88300 KB Output is correct
28 Correct 1520 ms 88332 KB Output is correct
29 Correct 1436 ms 88220 KB Output is correct
30 Correct 1596 ms 88240 KB Output is correct
31 Correct 1246 ms 88240 KB Output is correct
32 Correct 1274 ms 88544 KB Output is correct
33 Correct 1290 ms 88708 KB Output is correct
34 Correct 1646 ms 88704 KB Output is correct
35 Correct 1546 ms 88628 KB Output is correct
36 Execution timed out 2045 ms 88496 KB Time limit exceeded
37 Halted 0 ms 0 KB -