#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int BIG = 123456789;
vector<int> ans;
struct SegTree {
int val = 0;
int lx, rx, mid;
int lb = 0, rb = BIG; // bounds
SegTree *ls = nullptr, *rs = nullptr;
SegTree(int l, int r) {
lx = l;
rx = r;
mid = (lx + rx)/2;
if(r - l > 1) {
int mid = (l + r)/2;
ls = new SegTree(l, mid);
rs = new SegTree(mid, r);
}
}
void updateRight(int k) { // Min value, pushes everything on the right
if(k >= rb) return;
val = min(val, k);
if(k >= lb) {
rb = k;
return;
}
lb = rb = k;
}
void updateLeft(int k) { // Max value, pushes everything on the left
if(k <= lb) return;
val = max(val, k);
if(k <= rb) {
lb = k;
return;
}
lb = rb = k;
}
void prop() {
//cout << "Nice one " << lx << ' ' << rx << ' ' << lb << ' ' << rb << ' '<< val <<"\n";
if(ls == nullptr) return;
ls->updateLeft(lb);
ls->updateRight(rb);
rs->updateLeft(lb);
rs->updateRight(rb);
lb = 0; rb = BIG;
}
void setMin(int l, int r, int k) {
prop();
if(l >= rx || lx >= r) return;
if(l <= lx && rx <= r) {
updateRight(k);
return;
}
ls->setMin(l, r, k);
rs->setMin(l, r, k);
}
void setMax(int l, int r, int k) {
prop();
if(l >= rx || lx >= r) return;
if(l <= lx && rx <= r) {
updateLeft(k);
return;
}
ls->setMax(l, r, k);
rs->setMax(l, r, k);
}
void getAll() {
prop();
if(rx - lx == 1) {
ans[lx] = val;
return;
}
ls->getAll();
rs->getAll();
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int siz = 1;
while(siz <= n) siz *= 2;
SegTree st(0, siz);
ans.resize(siz);
for(int i = 0; i < k; i++) {
//cout << "Doing " << i << '\n';
if(op[i] == 2) st.setMin(left[i], right[i]+1, height[i]);
if(op[i] == 1) st.setMax(left[i], right[i]+1, height[i]);
}
st.getAll();
for(int i = 0; i < n; i++) finalHeight[i] = ans[i];
return;
}
