Submission #18616

#	Time	Username	Problem	Language	Result	Execution time	Memory
18616		mindol	Wall (IOI14_wall)	C++14	100 / 100	2597 ms	248220 KiB

wall

#include<algorithm>
#include<vector>
using namespace std;

int res[1<<21];

struct Lazy{ int type,value; };
vector<Lazy> lazy[1<<22]; // type이 0이면 하한, 1이면 상한 설정.
int base=1<<21;

void check(int type,int value,int now)
{
    if(lazy[now].size()==0) lazy[now].push_back({type,value});
    else if(lazy[now].size()==1)
    {
        if(lazy[now][0].type==type)
        {
            if(lazy[now][0].type==0) lazy[now][0].value=max(lazy[now][0].value,value);
            else lazy[now][0].value=min(lazy[now][0].value,value);
        }
        else lazy[now].push_back({type,value});
    }
    else
    {
        if(lazy[now][0].type==0) // lazy[now][1].type은 1이다.
        {
            if(type==1) lazy[now][1].value=min(lazy[now][1].value,value);
            else
            {
                if(value >= lazy[now][0].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
                else if(value >= lazy[now][1].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
            }
        }
        else // lazy[now][0].type은 1, lazy[now][1].type은 0이다.
        {
            if(type==0) lazy[now][1].value=max(lazy[now][1].value,value);
            else
            {
                if(value <= lazy[now][0].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
                else if(value <= lazy[now][1].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
            }
        }
    }
}

void lazydown(int now,int now_l,int now_r)
{
    for(int i=0;i<lazy[now].size();i++)
    {
        int type=lazy[now][i].type, value=lazy[now][i].value;
        if(now_l == now_r)
        {
            int index = now-base+1;
            if(type==0) res[index]=max(res[index],value);
            else res[index]=min(res[index],value);
        }
        else
        {
            check(type,value,now*2);
            check(type,value,now*2+1);
        }
    }
    lazy[now].clear();
}

void update(int l,int r,int type,int value,int now,int now_l,int now_r)
{
    lazydown(now,now_l,now_r);
    if(now_l>r || now_r<l) return;
    else if(l<=now_l && now_r<=r)
    {
        check(type,value,now);
        lazydown(now,now_l,now_r);
    }
    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)
{
    lazydown(now,now_l,now_r);
    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[])
{
    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]=res[i+1];
}

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