#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> low, high;
void apply(int p, int lo, int hi) {
low[p] = min(max(lo, low[p]), hi);
high[p] = min(max(lo, high[p]), hi);
}
void push(int p) {
apply(p << 1, low[p], high[p]);
apply(p << 1 | 1, low[p], high[p]);
low[p] = 0;
high[p] = 1e9;
}
void update(int p, int l, int r, int ql, int qr, int lo, int hi) {
if (qr < l || ql > r)
return;
if (ql <= l && qr >= r) {
apply(p, lo, hi);
return;
}
push(p);
int m = (l + r) >> 1;
update(p << 1, l, m, ql, qr, lo, hi);
update(p << 1 | 1, m + 1, r, ql, qr, lo, hi);
}
int *f;
void collect(int p, int l, int r) {
if (l == r) {
*(f + l) = low[p];
return;
}
push(p);
int m = (l + r) >> 1;
collect(p << 1, l, m);
collect(p << 1 | 1, m + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
low.resize(4 * n);
high.assign(4 * n, 1e9);
for (int i = 0; i < k; ++i) {
if (op[i] == 1) {
update(1, 0, n - 1, left[i], right[i], height[i], 1e9);
} else {
update(1, 0, n - 1, left[i], right[i], 0, height[i]);
}
}
f = finalHeight;
collect(1, 0, n - 1);
return;
}
