oj.uz

Submission #574327

# Submission time Handle Problem Language Result Execution time Memory
574327 2022-06-08T10:50:21 Z mosiashvililuka Wall (IOI14_wall) C++14
100 / 100
 794 ms 93800 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N=100009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,ans[2000009],tes,t,tp,l,r,zl,zr,za,segl[8000009],segr[8000009],segt[8000009];
void CHANGE(int rr, int l, int r, int t){
    if(t!=N){
        segl[rr]=-N;segr[rr]=N;segt[rr]=t;
        return;
    }
    if(segt[rr]!=N){
        segt[rr]=max(segt[rr],l);
        segt[rr]=min(segt[rr],r);
        return;
    }
    if(l>segr[rr]){
        segl[rr]=-N;segr[rr]=N;segt[rr]=l;
        return;
    }
    if(r<segl[rr]){
        segl[rr]=-N;segr[rr]=N;segt[rr]=r;
        return;
    }
    segl[rr]=max(segl[rr],l);
    segr[rr]=min(segr[rr],r);
}
void pushdown(int q, int w, int rr){
    CHANGE(rr*2,segl[rr],segr[rr],segt[rr]);
    CHANGE(rr*2+1,segl[rr],segr[rr],segt[rr]);
    segl[rr]=-N;segr[rr]=N;segt[rr]=N;
}
void upd(int q, int w, int rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        CHANGE(rr,zl,zr,N);
        return;
    }
    pushdown(q,w,rr);
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
}
void buildWall(int Nn, int Kk, int Oop[], int Lleft[], int Rright[], int Hheight[], int finalHeight[]){
    a=Nn;tes=Kk;
    za=1;
    while(za<a) za*=2;
    for(i=0; i<=za*2; i++){
        segl[i]=-N;segr[i]=N;segt[i]=N;
    }
    for(t=1; t<=tes; t++){
        tp=Oop[t-1];
        if(tp==2){
            l=Lleft[t-1]+1;r=Rright[t-1]+1;zl=-N;zr=Hheight[t-1];
            upd(1,za,1);
        }else{
            l=Lleft[t-1]+1;r=Rright[t-1]+1;zl=Hheight[t-1];zr=N;
            upd(1,za,1);
        }
    }
    for(i=1; i<=a; i++){
        c=za+i-1;zx=0;
        while(c!=0){
            if(segt[c]!=N){
                zx=segt[c];
                c/=2;
                continue;
            }
            zx=max(zx,segl[c]);
            zx=min(zx,segr[c]);
            c/=2;
        }
        ans[i]=zx;
    }
    //
    for(i=1; i<=a; i++){
        finalHeight[i-1]=ans[i];
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 1020 KB Output is correct
5 Correct 5 ms 956 KB Output is correct
6 Correct 6 ms 920 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 140 ms 13908 KB Output is correct
3 Correct 177 ms 8228 KB Output is correct
4 Correct 457 ms 21740 KB Output is correct
5 Correct 303 ms 22884 KB Output is correct
6 Correct 278 ms 21308 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 1020 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 6 ms 960 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 141 ms 13900 KB Output is correct
9 Correct 158 ms 8308 KB Output is correct
10 Correct 434 ms 21880 KB Output is correct
11 Correct 302 ms 22896 KB Output is correct
12 Correct 306 ms 21400 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 132 ms 13896 KB Output is correct
15 Correct 28 ms 2252 KB Output is correct
16 Correct 503 ms 22016 KB Output is correct
17 Correct 301 ms 21452 KB Output is correct
18 Correct 315 ms 21416 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 5 ms 892 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 158 ms 13896 KB Output is correct
9 Correct 156 ms 8280 KB Output is correct
10 Correct 422 ms 21764 KB Output is correct
11 Correct 311 ms 22832 KB Output is correct
12 Correct 310 ms 21208 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 130 ms 13936 KB Output is correct
15 Correct 29 ms 2288 KB Output is correct
16 Correct 467 ms 22044 KB Output is correct
17 Correct 307 ms 21436 KB Output is correct
18 Correct 296 ms 21440 KB Output is correct
19 Correct 777 ms 93732 KB Output is correct
20 Correct 775 ms 91292 KB Output is correct
21 Correct 754 ms 93780 KB Output is correct
22 Correct 783 ms 91348 KB Output is correct
23 Correct 793 ms 91304 KB Output is correct
24 Correct 737 ms 91300 KB Output is correct
25 Correct 794 ms 91296 KB Output is correct
26 Correct 782 ms 93724 KB Output is correct
27 Correct 759 ms 93800 KB Output is correct
28 Correct 752 ms 91316 KB Output is correct
29 Correct 752 ms 91312 KB Output is correct
30 Correct 732 ms 91364 KB Output is correct