#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INFINI = 1000 * 1000 * 1000;
struct Label {
int mini, maxi;
Label(int _mini = 0, int _maxi = INFINI) {
mini = _mini;
maxi = _maxi;
}
};
void append_label(Label& lbl, Label f) {
lbl.mini = max(lbl.mini, f.mini);
lbl.maxi = max(lbl.mini, lbl.maxi);
lbl.maxi = min(lbl.maxi, f.maxi);
lbl.mini = min(lbl.mini, lbl.maxi);
}
Label labels[(1 << 22)];
void push(int n) {
if(n >= (1 << 21)) return;
append_label(labels[2 * n], labels[n]);
append_label(labels[2 * n + 1], labels[n]);
labels[n] = Label();
}
void update(int l, int r, Label lbl, int n = 1, int ll = 0, int rr = (1 << 21)) {
push(n);
if(r <= ll || rr <= l) return;
if(l <= ll && rr <= r) {
append_label(labels[n], lbl);
return;
}
int mm = (ll + rr) / 2;
update(l, r, lbl, 2 * n, ll, mm);
update(l, r, lbl, 2 * n + 1, mm, rr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for(int iOp = 0;iOp < k;iOp++) {
int l = left[iOp], r = right[iOp] + 1, h = height[iOp];
if(op[iOp] == 1) {
// Adding phase
update(l, r, {h, INFINI});
}
else {
// Removing phase
update(l, r, {0, h});
}
}
for(int iPos = 0;iPos < n;iPos++) {
update(iPos, iPos + 1, {});
finalHeight[iPos] = labels[(1 << 21) + iPos].mini;
}
}
