#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
const int maxn = 2e6;
struct seg
{
ll mi,mx;
};
bool gen;
seg tree[maxn*4];
seg lz[maxn*4];
int N,tek;
void pull_down(int p,ll val)
{
lz[p].mi=min(lz[p].mi,val);
lz[p].mx=min(lz[p].mx,val);
tree[p].mi=min(tree[p].mi,val);
tree[p].mx=min(tree[p].mx,val);
}
void pull_up(int p,ll val)
{
lz[p].mx=max(lz[p].mx,val);
lz[p].mi=max(lz[p].mi,val);
tree[p].mi=max(tree[p].mi,val);
tree[p].mx=max(tree[p].mx,val);
}
void push_lazy(int p)
{
if(lz[p].mi!=INT_MIN)
{
if(p*2<=4*N)
pull_up(p*2,lz[p].mi);
if(p*2+1<=4*N)
pull_up(p*2+1,lz[p].mi);
}
if(lz[p].mx!=INT_MAX)
{
if(p*2<=4*N)
pull_down(p*2,lz[p].mx);
if(p*2+1<=4*N)
pull_down(p*2+1,lz[p].mx);
}
lz[p] = {INT_MIN,INT_MAX};
}
void update(int ql,int qr,int type,ll val,int p=1,int l=0,int r=N-1)
{
//cout<<ql<<" "<<qr<<" "<<p<<" "<<l<<" "<<r<<endl;
push_lazy(p);
if(l>qr || r<ql)
return ;
if(l>=ql && r<=qr)
{
if(type==2)
{
pull_down(p,val);
}
else
{
pull_up(p,val);
}
return ;
}
update(ql,qr,type,val,p*2,l,(l+r)/2);
update(ql,qr,type,val,p*2+1,(l+r)/2+1,r);
}
void query(int q,int p=1,int l=0,int r=N-1)
{
push_lazy(p);
if(q<l || q>r)
return ;
if(l==q && r==q)
{
tek = tree[p].mi;
return ;
}
query(q,p*2,l,(l+r)/2);
query(q,p*2+1,(l+r)/2+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
N=n;
//cout<<"do tuka"<<endl;
for(int i=0; i<k; i++)
{
if(op[i]==2)
update(left[i],right[i],2,height[i]);///namalqvane => namirane na max stoinost
else update(left[i],right[i],1,height[i]);///uvelichavane => namirane na min stoinost
}
for(int i=0; i<n; i++)
{
tek=0;
query(i);
finalHeight[i] = tek;
}
}
