#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = LLONG_MAX;
struct node
{
ll down_lim=0;
ll up_lim=INF;
};
node aint[810001];
void propagate(int nod)
{
aint[nod*2].up_lim = min(aint[nod*2].up_lim, aint[nod].up_lim);
aint[nod*2].down_lim = min(aint[nod*2].down_lim, aint[nod*2].up_lim);
aint[nod*2].down_lim = max(aint[nod*2].down_lim, aint[nod].down_lim);
aint[nod*2].up_lim = max(aint[nod*2].up_lim, aint[nod*2].down_lim);
aint[nod*2+1].up_lim = min(aint[nod*2+1].up_lim, aint[nod].up_lim);
aint[nod*2+1].down_lim = min(aint[nod*2+1].down_lim, aint[nod*2+1].up_lim);
aint[nod*2+1].down_lim = max(aint[nod*2+1].down_lim, aint[nod].down_lim);
aint[nod*2+1].up_lim = max(aint[nod*2+1].up_lim, aint[nod*2+1].down_lim);
}
void upd2(ll nod, ll st, ll dr, ll le, ll ri, ll newh)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
aint[nod].up_lim = min(aint[nod].up_lim, newh);
aint[nod].down_lim = min(aint[nod].down_lim, aint[nod].up_lim);
return;
}
ll mij=(st+dr)/2;
propagate(nod);
upd2(nod*2,st,mij,le,min(mij,ri),newh);
upd2(nod*2+1,mij+1,dr,max(mij+1,le),ri,newh);
}
void upd1(ll nod, ll st, ll dr, ll le, ll ri, ll newh)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
aint[nod].down_lim = max(aint[nod].down_lim, newh);
aint[nod].up_lim = max(aint[nod].up_lim, aint[nod].down_lim);
return;
}
ll mij=(st+dr)/2;
propagate(nod);
upd1(nod*2,st,mij,le,min(mij,ri),newh);
upd1(nod*2+1,mij+1,dr,max(mij+1,le),ri,newh);
}
ll rez[200001];
void get_rez(ll nod, ll st, ll dr)
{
if(st==dr)
{
if(aint[nod].up_lim == aint[nod].down_lim)
rez[st]=aint[nod].up_lim;
else
rez[st]=aint[nod].down_lim;
return;
}
propagate(nod);
ll mij=(st+dr)/2;
get_rez(nod*2,st,mij);
get_rez(nod*2+1,mij+1,dr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i=0;i<n;i++)
rez[i] = 0;
for(int i=0;i<k;i++)
{
if(op[i]==1)
upd1(1,0,n-1,left[i],right[i],height[i]);
else
upd2(1,0,n-1,left[i],right[i],height[i]);
}
get_rez(1,0,n-1);
for(int i=0;i<n;i++)
finalHeight[i]=rez[i];
return;
}
/**
*/
