#include "wall.h"
#include <bits/stdc++.h>
constexpr int inf = 500000;
struct node {
int l;
int r;
// clamp(a, l, r)
};
node merge(node a, node b) {
a.l = std::min(b.r, a.l);
a.r = std::min(b.r, a.r);
a.l = std::max(b.l, a.l);
a.r = std::max(b.l, a.r);
return a;
}
node id = {-inf, inf};
int eval(int x, node p) {
return std::max(p.l, std::min(p.r, x));
}
class segtree {
int n, size;
std::vector<node> data;
void update(int i) {
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
public:
segtree(int n_) : n(n_) {
size = 1;
while (size < n) {
size *= 2;
}
data.assign(2 * size, id);
}
void edit(int i, node v) {
i += size;
data[i] = v;
while (i != 1) {
i /= 2;
update(i);
}
}
node foldAll() {
return data[1];
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
std::vector<std::vector<int>> addList(n + 1), eraseList(n + 1);
for (int i = 0; i < k; ++i) {
addList[left[i]].push_back(i);
eraseList[right[i] + 1].push_back(i);
}
segtree seg(k);
for (int i = 0; i < n; ++i) {
for (const int x : addList[i]) {
if (op[x] == 1) {
seg.edit(x, {height[x], inf});
} else {
seg.edit(x, {-inf, height[x]});
}
}
for (const int x : eraseList[i]) {
seg.edit(x, id);
}
const auto res = seg.foldAll();
finalHeight[i] = eval(0, res);
}
}
