Submission #18617

#	Time	Username	Problem	Language	Result	Execution time	Memory
18617		mindol	Wall (IOI14_wall)	C++14	100 / 100	1422 ms	49492 KiB

wall

#include<algorithm>
using namespace std;

int lo[1<<22],hi[1<<22],base=1<<21;

void init()
{
    int sz=1<<22;
    for(int i=1;i<sz;i++)
        lo[i]=0, hi[i]=100000;
}

void down(int now)
{
    if(now>=base) return;
    hi[now*2]=min(max(hi[now*2],lo[now]),hi[now]);
    lo[now*2]=max(min(lo[now*2],hi[now]),lo[now]);
    hi[now*2+1]=min(max(hi[now*2+1],lo[now]),hi[now]);
    lo[now*2+1]=max(min(lo[now*2+1],hi[now]),lo[now]);
    lo[now]=0, hi[now]=100000;
}

void update(int l,int r,int type,int value,int now,int now_l,int now_r)
{
    down(now);
    if(now_r<l || now_l>r) return;
    else if(l<=now_l && now_r<=r)
    {
        if(type==0)
        {
            lo[now]=max(lo[now],value);
            hi[now]=max(hi[now],value);
        }
        else
        {
            hi[now]=min(hi[now],value);
            lo[now]=min(lo[now],value);
        }
        down(now);
    }
    else
    {
        int mid=(now_l+now_r)/2;
        update(l,r,type,value,now*2,now_l,mid);
        update(l,r,type,value,now*2+1,mid+1,now_r);
    }
}

void make_res(int now,int now_l,int now_r)
{
    down(now);
    if(now_l==now_r) return;
    int mid=(now_l+now_r)/2;
    make_res(now*2,now_l,mid);
    make_res(now*2+1,mid+1,now_r);
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
    init();
    for(int i=0;i<k;i++)
        update(left[i]+1,right[i]+1,op[i]-1,height[i],1,1,base);
    make_res(1,1,base);
    for(int i=0;i<n;i++)
        finalHeight[i]=lo[i+base];
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39