제출 #305070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305070		vipghn2003	벽 (IOI14_wall)	C++14	0 / 100	1 ms	512 KiB

wall

#include<bits/stdc++.h>

using namespace std;
const int N=2e6+5;
int STmn[4*N],STmx[4*N],lazymin[4*N],lazymax[4*N],res[N];

void build(int id,int l,int r)
{
    lazymin[id]=1e9;
    lazymax[id]=0;
    if(l==r) return ;
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}

void dolazy(int id,int l,int r)
{
    STmn[id]=min(STmn[id],lazymin[id]);
    STmn[id]=max(STmn[id],lazymax[id]);
    STmx[id]=min(STmx[id],lazymin[id]);
    STmx[id]=max(STmx[id],lazymax[id]);
    if(l!=r)
    {
        lazymin[id*2]=min(lazymin[id*2],lazymin[id]);
        lazymin[id*2+1]=min(lazymin[id*2+1],lazymin[id]);
        lazymin[id*2]=max(lazymin[id*2],lazymax[id]);
        lazymin[id*2+1]=max(lazymin[id*2+1],lazymax[id]);
        lazymax[id*2+1]=min(lazymax[id*2+1],lazymin[id]);
        lazymax[id*2]=min(lazymax[id*2],lazymin[id]);
        lazymax[id*2+1]=max(lazymax[id*2+1],lazymax[id]);
        lazymax[id*2]=max(lazymax[id*2],lazymax[id]);
    }
    lazymax[id]=0;
    lazymin[id]=1e9;
}

void update(int id,int l,int r,int L,int R,int type,int val)
{
    dolazy(id,l,r);
    if(R<l||r<L) return;
    if(L<=l&&r<=R)
    {
        if(type==1)
        {
            lazymin[id]=max(lazymin[id],val);
            lazymax[id]=max(lazymax[id],val);
        }
        else if(type==2)
        {
            lazymin[id]=min(lazymin[id],val);
            lazymax[id]=min(lazymax[id],val);
        }
        dolazy(id,l,r);
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,L,R,type,val);
    update(id*2+1,mid+1,r,L,R,type,val);
    STmx[id]=max(STmx[id*2],STmx[id*2+1]);
    STmn[id]=min(STmn[id*2],STmn[id*2+1]);
}

void comp(int id, int l, int r)
{
    dolazy(id,l,r);
    if(l==r)
    {
        res[l]=STmn[id];
        return;
    }
    int mid=(l+r)/2;
    comp(id*2,l,mid);
    comp(id*2+1,mid+1,r);
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
    build(1,1,n);
    for(int i=0;i<k;i++)
    {
        left[i]++;
        right[i]++;
        update(1,1,n,left[i],right[i],op[i],height[i]);
    }
    comp(1,1,n);
    for(int i=0;i<n;i++) finalHeight[i]=res[i-1];
}

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