#include <bits/stdc++.h>
#include "wall.h"
#define for0(i, n) for(int i = 0; i < int(b); ++ i)
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2e6;
pii st[4 * maxn + 1];
int valu[maxn];
void built(int nodo, int l, int r){
st[nodo] = mp(0, 0);
if(l == r){
return;
}
int mitad = (l + r) / 2;
built(nodo * 2, l, mitad);
built(nodo * 2 + 1, mitad + 1, r);
}
void update(int nodo, int l, int r, int a, int b, bool tipo, int val){
if(l != r && st[nodo].fi == st[nodo].se){
st[nodo * 2] = st[nodo];
st[nodo * 2 + 1] = st[nodo];
}
if(r < a || l > b){
return;
}
if(l >= a && r <= b){
if(tipo){
if(st[nodo].se >= val){
return;
}
if(st[nodo].fi < val){
st[nodo] = mp(val, val);
return;
}
}
else{
if(st[nodo].fi <= val){
return;
}
if(st[nodo].se > val){
st[nodo] = mp(val, val);
return;
}
}
}
int mitad = (l + r) / 2;
update(nodo * 2, l, mitad, a, b, tipo, val);
update(nodo * 2 + 1, mitad + 1, r, a, b, tipo, val);
st[nodo] = mp(max(st[nodo * 2].fi, st[nodo * 2 + 1].fi), min(st[nodo * 2].se, st[nodo * 2 + 1].se));
}
void query(int nodo, int l, int r){
if(st[nodo].fi == st[nodo].se){
forn(i, l, r){
valu[i] = st[nodo].fi;
}
return;
}
int mitad = (l + r) / 2;
query(nodo * 2, l, mitad);
query(nodo * 2 + 1, mitad + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
built(1, 0, n - 1);
for(int i = 0; i < k; ++ i){
bool opcion = (op[i] == 1);
update(1, 0, n - 1, left[i], right[i], opcion, height[i]);
}
query(1, 0, n - 1);
for(int i = 0; i < n; ++ i){
finalHeight[i] = valu[i];
}
}
