Submission #18615

#	Time	Username	Problem	Language	Result	Execution time	Memory
18615		mindol	Wall (IOI14_wall)	C++14	61 / 100	2965 ms	262144 KiB

wall

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

struct Node{ int Max,Min; };
Node tree[1<<22]; // 구간의 최대, 최소

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(type==0) // 모든 값이 value 이상이 된다.
        {
            tree[now].Min=max(tree[now].Min,value);
            tree[now].Max=max(tree[now].Max,value);
        }
        else // 모든 값이 value 이하가 된다.
        {
            tree[now].Max=min(tree[now].Max,value);
            tree[now].Min=min(tree[now].Min,value);
        }

        if(now_l!=now_r)
        {
            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);
        tree[now].Max=max(tree[now*2].Max,tree[now*2+1].Max);
        tree[now].Min=max(tree[now*2].Min,tree[now*2+1].Min);
    }
}

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]=tree[base+i].Min;
}

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