Submission #574327

#	Time	Username	Problem	Language	Result	Execution time	Memory
574327		mosiashvililuka	Wall (IOI14_wall)	C++14	100 / 100	794 ms	93800 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39