#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct lz {
int min, max;
};
struct sgt {
int n;
vector<int> arr;
vector<lz> lazy;
void init(int sz) {
n = sz;
arr.assign(n+10, 0);
lazy.assign(4*sz+10, {0, (int)1e9});
}
lz merge(lz bf, lz af) {
lz nw;
nw.max = min(bf.max, af.max);
nw.min = max(af.min, bf.min);
if(nw.max < nw.min) {
if(nw.min == af.min) nw.max = nw.min;
else nw.min = nw.max;
}
return nw;
}
void push(int l, int r, int node) {
if(l != r) {
lazy[node*2+1] = merge(lazy[node*2+1], lazy[node]);
lazy[node*2+2] = merge(lazy[node*2+2], lazy[node]);
lazy[node] = {0, (int)1e9};
}
}
void update(int l, int r, int idl, int idr, lz val, int node) {
push(l, r, node);
if(l > idr || r < idl) return;
if(l >= idl && r <= idr) {
lazy[node] = merge(lazy[node], val);
push(l, r, node);
return;
}
int mid = (l+r)/2;
update(l, mid, idl, idr, val, node*2+1);
update(mid+1, r, idl, idr, val, node*2+2);
}
void get(int l, int r, int node) {
push(l, r, node);
if(l == r) {
arr[l] = lazy[node].min;
return;
}
int mid = (l+r)/2;
get(l, mid, node*2+1);
get(mid+1, r, node*2+2);
}
void upd(int idl, int idr, lz val) {
update(0, n, idl, idr, val, 0);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
sgt seg;
seg.init(n);
for(int i=0; i<k; i++) {
lz val = {0, (int)1e9};
if(op[i] == 1) val.min = height[i];
else val.max = height[i];
seg.upd(left[i], right[i], val);
}
seg.get(0, n, 0);
for(int i=0; i<n; i++) finalHeight[i] = seg.arr[i];
}
