제출 #112456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
112456		ansol4328	벽 (IOI14_wall)	C++11	100 / 100	1099 ms	92280 KiB

wall

#include<vector>
#include<algorithm>

using namespace std;

struct SegTree
{
    vector<int> MaxT, MinT;
    vector<int> MaxLazy, MinLazy;
    int base;
    SegTree(int a)
    {
        base=1;
        while(base<a) base<<=1;
        MaxT.resize(base*2+2);
        MinT.resize(base*2+2);
        MaxLazy.resize(base*2+2,-1);
        MinLazy.resize(base*2+2,-1);
        base--;
    }
    void propagate(int ns, int nf, int num)
    {
        int a, b, c;
        if(MaxLazy[num]!=-1)
        {
            c=MaxLazy[num];
            if(ns<nf)
            {
                a=MinT[num*2], b=MaxT[num*2];
                if(MinLazy[num*2]!=-1) a=MinLazy[num*2];
                if(MaxLazy[num*2]!=-1) b=MaxLazy[num*2];
                if(c<a) MaxLazy[num*2]=MinLazy[num*2]=c;
                else if(a<=c && c<b) MaxLazy[num*2]=c;

                a=MinT[num*2+1], b=MaxT[num*2+1];
                if(MinLazy[num*2+1]!=-1) a=MinLazy[num*2+1];
                if(MaxLazy[num*2+1]!=-1) b=MaxLazy[num*2+1];
                if(c<a) MaxLazy[num*2+1]=MinLazy[num*2+1]=c;
                else if(a<=c && c<b) MaxLazy[num*2+1]=c;
            }
            MaxT[num]=c;
            MaxLazy[num]=-1;
        }
        if(MinLazy[num]!=-1)
        {
            c=MinLazy[num];
            if(ns<nf)
            {
                a=MinT[num*2], b=MaxT[num*2];
                if(MinLazy[num*2]!=-1) a=MinLazy[num*2];
                if(MaxLazy[num*2]!=-1) b=MaxLazy[num*2];
                if(a<c && c<=b) MinLazy[num*2]=c;
                else if(b<c) MinLazy[num*2]=MaxLazy[num*2]=c;

                a=MinT[num*2+1], b=MaxT[num*2+1];
                if(MinLazy[num*2+1]!=-1) a=MinLazy[num*2+1];
                if(MaxLazy[num*2+1]!=-1) b=MaxLazy[num*2+1];
                if(a<c && c<=b) MinLazy[num*2+1]=c;
                else if(b<c) MinLazy[num*2+1]=MaxLazy[num*2+1]=c;
            }
            MinT[num]=c;
            MinLazy[num]=-1;
        }
    }
    void oper(int op, int v, int st, int fn, int ns=1, int nf=-1, int num=1)
    {
        if(nf==-1) nf=base+1;
        propagate(ns,nf,num);
        if(fn<ns || nf<st) return;
        if(st<=ns && nf<=fn)
        {
            int a=MinT[num], b=MaxT[num], c=v;
            if(op==1)
            {
                if(a<c && c<=b) MinLazy[num]=c;
                else if(b<c) MinLazy[num]=MaxLazy[num]=c;
            }
            else if(op==2)
            {
                if(c<a) MaxLazy[num]=MinLazy[num]=c;
                else if(a<=c && c<b) MaxLazy[num]=c;
            }
            propagate(ns,nf,num);
            return;
        }
        int mid=(ns+nf)>>1;
        oper(op,v,st,fn,ns,mid,num*2);
        oper(op,v,st,fn,mid+1,nf,num*2+1);
        MinT[num]=min(MinT[num*2],MinT[num*2+1]);
        MaxT[num]=max(MaxT[num*2],MaxT[num*2+1]);
    }
    void get_res()
    {
        int len=base+1, num=1;
        while(len!=0)
        {
            for(int ns=1 ; ns<=base+1 ; ns+=len)
            {
                propagate(ns,ns+len-1,num);
                num++;
            }
            len>>=1;
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	SegTree T(n);
  	for(int i=0 ; i<k ; i++)
    {
      	left[i]++, right[i]++;
        T.oper(op[i],height[i],left[i],right[i]);
    }
  	T.get_res();
  	for(int i=0 ; i<n ; i++) finalHeight[i]=T.MinT[T.base+i+1];
}

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