#include <bits/stdc++.h>
using namespace std;
int clamp(int val, pair<int,int> bounds) {
return max(bounds.first, min(bounds.second,val));
}
pair<int,int> compose_clamps(pair<int,int> outside, pair<int,int> inside) {
if (outside.second <= inside.first) return {outside.second, outside.second};
if (outside.first >= inside.second) return {outside.first, outside.first};
return {max(outside.first,inside.first), min(outside.second,inside.second)};
}
struct Node {
int l;
int r;
Node *ln;
Node *rn;
pair<int,int> bounds;
Node(int tl, int tr): l(tl), r(tr) {
bounds = {INT_MIN,INT_MAX};
if (l + 1 == r) {
ln = rn = NULL;
return;
}
int mid = (l + r) / 2;
ln = new Node(l, mid);
rn = new Node(mid, r);
}
int get(int i) {
if (l <= i && i < r) {
if (l + 1 == r) {
return clamp(0, bounds);
}
return clamp(ln->get(i) + rn->get(i), bounds);
}
return 0;
}
void avoid_responsibility() {
ln->bounds = compose_clamps(bounds, ln->bounds);
rn->bounds = compose_clamps(bounds, rn->bounds);
bounds = {INT_MIN,INT_MAX};
}
void apply(int lb, int rb, pair<int,int> bds) {
if (rb <= l || r <= lb) return;
if (lb <= l && r <= rb) {
bounds = compose_clamps(bds, bounds);
return;
}
avoid_responsibility();
ln->apply(lb, rb, bds);
rn->apply(lb, rb, bds);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
Node *root = new Node(0, n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
root->apply(left[i], right[i] + 1, {height[i],INT_MAX});
} else {
root->apply(left[i], right[i] + 1, {INT_MIN,height[i]});
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = root->get(i);
}
}
