#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1000000000;
struct func{
int l,r;
};
func compose(func f,func g)
{
if(f.r<=g.l) return {g.l,g.l};
if(f.l>=g.r) return {g.r,g.r};
return {max(f.l,g.l),min(f.r,g.r)};
}
int n,k;
func seg[8000010];
bool marked[8000010],bottom[8000010];
int pos[2000010];
void build(int v,int st,int ed)
{
marked[v]=false;
bottom[v]=false;
seg[v]={-INF,INF};
if(st==ed)
{
pos[st]=v;
bottom[v]=true;
return;
}
int mid=(st+ed)>>1;
build(v<<1,st,mid);
build(1+(v<<1),mid+1,ed);
}
void push_down(int v)
{
if(!marked[v] || bottom[v]) return;
marked[v]=false;
marked[v<<1]=marked[1+(v<<1)]=true;
seg[v<<1]=compose(seg[v<<1],seg[v]);
seg[1+(v<<1)]=compose(seg[1+(v<<1)],seg[v]);
seg[v]={-INF,INF};
}
void upd(int v,int l,int r,int st,int ed,func f)
{
if(st>ed) return;
if(l==st && r==ed)
{
marked[v]=true;
seg[v]=compose(seg[v],f);
return;
}
push_down(v);
int mid=(l+r)>>1;
upd(v<<1,l,mid,st,min(mid,ed),f);
upd(1+(v<<1),mid+1,r,max(mid+1,st),ed,f);
}
int que(int x)
{
int ver=pos[x],res=0;
while(ver)
{
if(res<=seg[ver].l) res=seg[ver].l;
else if(res>=seg[ver].r) res=seg[ver].r;
ver>>=1;
}
return res;
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
n=N;
k=K;
build(1,0,n-1);
for(int i=0;i<k;i++)
{
if(op[i]==1)
{
upd(1,0,n-1,left[i],right[i],{height[i],INF});
}
else
{
upd(1,0,n-1,left[i],right[i],{-INF,height[i]});
}
}
for(int i=0;i<n;i++) finalHeight[i]=que(i);
return;
}
