# include <iostream>
# include <climits>
//# include "grader.cpp"
# include "wall.h"
using namespace std;
const int MAX=2e6+11;
int N;
int a[MAX];
struct node
{
int l,r;
node() {l=0;r=INT_MAX;}
node(int _l, int _r) {l=_l;r=_r;}
node friend operator + (node A, node B)
{
A.l=max(A.l,B.l);
A.r=max(A.l,A.r);
A.r=min(A.r,B.r);
A.l=min(A.l,A.r);
return A;
}
};
node lazy[MAX*4];
node tree[MAX*4];
void build(int v=1, int l=0, int r=N-1)
{
if(l==r)
{
tree[v]={0,0};
return ;
}
int mid=(l+r)/2;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
tree[v]=tree[v*2]+tree[v*2+1];
}
void push_lazy(int v, int l, int r)
{
if(lazy[v].l==0 and lazy[v].r==INT_MAX) return ;
tree[v]=tree[v]+lazy[v];
//cout<<l<<" "<<r<<":"<<tree[v].l<<" "<<tree[v].r<<"\n";
if(l!=r)
{
lazy[v*2]=lazy[v*2]+lazy[v];
lazy[v*2+1]=lazy[v*2+1]+lazy[v];
}
lazy[v]={0,INT_MAX};
}
void update(int le, int ri, node nd, int v=1, int l=0, int r=N-1)
{
push_lazy(v,l,r);
if(ri<l or r<le) return ;
if(le<=l and r<=ri)
{
lazy[v]=lazy[v]+nd;
push_lazy(v,l,r);
return ;
}
int mid=(l+r)/2;
update(le,ri,nd,v*2,l,mid);
update(le,ri,nd,v*2+1,mid+1,r);
tree[v]=tree[v*2]+tree[v*2+1];
}
int query(int pos, int v=1, int l=0, int r=N-1)
{
push_lazy(v,l,r);
if(l==r) return tree[v].l;
int mid=(l+r)/2;
if(pos<=mid) return query(pos,v*2,l,mid);
else return query(pos,v*2+1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
N=n;
build();
for(int i=0;i<k;i++)
{
if(op[i]==1) update(left[i],right[i],{height[i],INT_MAX});
else update(left[i],right[i],{0,height[i]});
}
for(int i=0;i<n;i++)
{
finalHeight[i]=query(i);
}
return;
}
/**
In:
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
Out:
0
0
0
39412
39412
39412
48623
48623
48623
48623
*/
/**
In:
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
Out:
3
4
5
4
3
3
0
0
1
0
*/
