#include <bits/stdc++.h>
#include "wall.h"
#define DIM 2000010
#define INF 2000000000
using namespace std;
struct segment_tree{
int mini,maxi; /// astea sunt lazy urile
} aint[DIM*4];
int sol[DIM];
void update_lazy (int nod, int st, int dr){
if (st == dr)
return;
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[fiu_st].maxi = min (aint[fiu_st].maxi,aint[nod].mini);
aint[fiu_st].mini = min (aint[fiu_st].mini,aint[nod].mini);
aint[fiu_st].mini = max (aint[fiu_st].mini,aint[nod].maxi);
aint[fiu_st].maxi = max (aint[fiu_st].maxi,aint[nod].maxi);
///
aint[fiu_dr].maxi = min (aint[fiu_dr].maxi,aint[nod].mini);
aint[fiu_dr].mini = min (aint[fiu_dr].mini,aint[nod].mini);
aint[fiu_dr].mini = max (aint[fiu_dr].mini,aint[nod].maxi);
aint[fiu_dr].maxi = max (aint[fiu_dr].maxi,aint[nod].maxi);
aint[nod].mini = INF, aint[nod].maxi = 0;
}
void build (int nod, int st, int dr){
aint[nod] = {INF,0};
if (st == dr)
return;
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
}
void update_maxi (int nod, int st, int dr, int x, int y, int val){
if (x <= st && dr <= y){
aint[nod].maxi = max (aint[nod].maxi,val);
aint[nod].mini = max (aint[nod].mini,val);
return;
}
update_lazy(nod,st,dr);
int mid = (st+dr)>>1;
if (x <= mid)
update_maxi (nod<<1,st,mid,x,y,val);
if (y > mid)
update_maxi ((nod<<1)|1,mid+1,dr,x,y,val);
}
void update_mini (int nod, int st, int dr, int x, int y, int val){
update_lazy(nod,st,dr);
if (x <= st && dr <= y){
aint[nod].mini = min (aint[nod].mini,val);
aint[nod].maxi = min (aint[nod].maxi,val);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update_mini (nod<<1,st,mid,x,y,val);
if (y > mid)
update_mini ((nod<<1)|1,mid+1,dr,x,y,val);
}
void get_elem (int nod, int st, int dr){
update_lazy (nod,st,dr);
if (st == dr){
sol[st] = aint[nod].maxi;
return;
}
int mid = (st+dr)>>1;
get_elem (nod<<1,st,mid);
get_elem ((nod<<1)|1,mid+1,dr);
}
void buildWall (int n, int k, int op[], int Left[], int Right[], int v[], int finalHeight[]){
build (1,0,n-1);
for (int i=0;i<k;i++){
if (op[i] == 1)
update_maxi (1,0,n-1,Left[i],Right[i],v[i]);
else update_mini (1,0,n-1,Left[i],Right[i],v[i]);
}
get_elem(1,0,n-1);
for (int i=0;i<n;i++)
finalHeight[i] = sol[i];
}
