#include "wall.h"
#include <algorithm>
#include <stdio.h>
#include <vector>

namespace
{

typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}

struct Seg
{
    Seg*L,*R;uint len,maxv,maxv2,minv,minv2;
    Seg(uint n):L(NULL),R(NULL),len(n),maxv(0),maxv2(0),minv(0),minv2(100000)
    {
        if(n>1)L=new Seg(n>>1),R=new Seg(n-(n>>1));
    }
#ifdef MYEE
    ~Seg(){if(len>1){delete L;delete R;}}
#endif
    voi Min(uint l,uint r,uint w)
    {
        if(l>=r||w>=maxv)return;
        if(!l&&r==len)
        {
            if(w<=minv){minv=maxv=w,minv2=1e5,maxv2=0;return;}
            if(w>=maxv2){maxv=w,_min(minv2,w);return;}
        }
        if(minv==maxv)L->minv=L->maxv=R->minv=R->maxv=minv,L->minv2=R->minv2=1e5,L->maxv2=R->maxv2=0;
        else
            _min(L->maxv,maxv),_min(R->maxv,maxv),_min(L->minv2,maxv),_min(R->minv2,maxv),
            _max(L->minv,minv),_max(R->minv,minv),_max(L->maxv2,minv),_max(R->maxv2,minv);
        if(l<(len>>1))
            if(r<=(len>>1))L->Min(l,r,w);
            else L->Min(l,len>>1,w),R->Min(0,r-(len>>1),w);
        else R->Min(l-(len>>1),r-(len>>1),w);
        minv=std::min(L->minv,R->minv),maxv=std::max(L->maxv,R->maxv),minv2=1e5,maxv2=0;
        _min(minv2,minv==L->minv?L->minv:L->minv2),_min(minv2,minv==R->minv?R->minv:R->minv2);
        _max(maxv2,maxv==L->maxv?L->maxv:L->maxv2),_max(maxv2,maxv==R->maxv?R->maxv:R->maxv2);
    }
    voi Max(uint l,uint r,uint w)
    {
        if(l>=r||w<=minv)return;
        if(!l&&r==len)
        {
            if(w>=maxv){minv=maxv=w,minv2=1e5,maxv2=0;return;}
            if(w<=minv2){minv=w,_max(maxv2,w);return;}
        }
        if(minv==maxv)L->minv=L->maxv=R->minv=R->maxv=minv,L->minv2=R->minv2=1e5,L->maxv2=R->maxv2=0;
        else
            _min(L->maxv,maxv),_min(R->maxv,maxv),_min(L->minv2,maxv),_min(R->minv2,maxv),
            _max(L->minv,minv),_max(R->minv,minv),_max(L->maxv2,minv),_max(R->maxv2,minv);
        if(l<(len>>1))
            if(r<=(len>>1))L->Max(l,r,w);
            else L->Max(l,len>>1,w),R->Max(0,r-(len>>1),w);
        else R->Max(l-(len>>1),r-(len>>1),w);
        minv=std::min(L->minv,R->minv),maxv=std::max(L->maxv,R->maxv),minv2=1e5,maxv2=0;
        _min(minv2,minv==L->minv?L->minv:L->minv2),_min(minv2,minv==R->minv?R->minv:R->minv2);
        _max(maxv2,maxv==L->maxv?L->maxv:L->maxv2),_max(maxv2,maxv==R->maxv?R->maxv:R->maxv2);
    }
    voi solve(std::vector<uint>&V)
    {
        if(len==1){V.push_back(minv);return;}
        if(minv==maxv)L->minv=L->maxv=R->minv=R->maxv=minv,L->minv2=R->minv2=1e5,L->maxv2=R->maxv2=0;
        else
            _min(L->maxv,maxv),_min(R->maxv,maxv),_min(L->minv2,maxv),_min(R->minv2,maxv),
            _max(L->minv,minv),_max(R->minv,minv),_max(L->maxv2,minv),_max(R->maxv2,minv);
        L->solve(V),R->solve(V);
    }
};

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    Seg S(n);
    for(int i=0;i<k;i++)
        if(op[i]==1)
            S.Max(left[i],right[i]+1,height[i]);
        else
            S.Min(left[i],right[i]+1,height[i]);
    std::vector<uint>V;S.solve(V);
    for(int i=0;i<n;i++)
        finalHeight[i]=V[i];
}

/*

g++ 25.cpp grader.cpp -o code -std=c++14 -DMYEE -Wall -fsanitize=undefined

time ./code

*/