#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct node {
int l, r, mx, mn;
node *left, *right;
void compose(int _mx, int _mn) {
if(_mx > mn)
mn = _mx;
if(_mn < mx)
mx = _mn;
mx = max(mx, _mx);
mn = min(mn, _mn);
}
void push() {
left->compose(mx, mn);
right->compose(mx, mn);
mx = 0;
mn = INF;
}
node(int l, int r) : l(l), r(r), mx(0), mn(INF) {
if(l < r) {
int m = (l + r) / 2;
left = new node(l, m);
right = new node(m + 1, r);
}
}
void upd(int rl, int rr, int mn, int mx) {
if(rr < l || r < rl)
return;
if(rl <= l && r <= rr) {
compose(mx, mn);
return;
}
push();
left->upd(rl, rr, mn, mx);
right->upd(rl, rr, mn, mx);
}
void trav(int* fi) {
if(l == r)
fi[l] = mx;
else {
push();
left->trav(fi);
right->trav(fi);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
node tree(0, n - 1);
for(int i = 0; i < k; i++) {
if(op[i] == 1)
tree.upd(left[i], right[i], INF, height[i]);
else
tree.upd(left[i], right[i], height[i], 0);
}
tree.trav(finalHeight);
return;
}
