#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
using namespace std;
const int INF = 1000000001;
struct st {
int lo, hi;
};
int n, k;
vector<st> lazy;
int *answer;
st merge(st &l, st &r) {
st res;
res.lo = max(l.lo, min(r.lo, l.hi));
res.hi = min(l.hi, max(r.hi, l.lo));
return res;
}
int ap(st &t, int x) {
return max(min(x, t.hi), t.lo);
}
void push(int k) {
if (lazy[k].lo == -INF and lazy[k].hi == INF) return;
lazy[k * 2] = merge(lazy[k], lazy[k * 2]);
lazy[k * 2 + 1] = merge(lazy[k], lazy[k * 2 + 1]);
lazy[k] = {-INF, INF};
}
void upd(int k, int l, int r, int ql, int qr, st op) {
if (qr < l or r < ql) return;
if (ql <= l and r <= qr) {
lazy[k] = merge(op, lazy[k]);
return;
}
push(k);
int m = (l + r) / 2;
upd(k * 2, l, m, ql, qr, op);
upd(k * 2 + 1, m + 1, r, ql, qr, op);
}
void get(int k, int l, int r, st acc) {
acc = merge(acc, lazy[k]);
if (l == r) {
answer[l] = ap(acc, 0);
return;
}
int m = (l + r) / 2;
get(k * 2, l, m, acc);
get(k * 2 + 1, m + 1, r, acc);
}
void buildWall(int N, int K, int op[], int ll[], int rr[], int height[], int finalHeight[]) {
n = N;
k = K;
answer = finalHeight;
if (n == 0) return;
lazy.assign(4 * n + 5, {-INF, INF});
for (int i = 0; i < k; ++i) {
st t;
if (op[i] == 1) t = {height[i], INF};
else t = {-INF, height[i]};
upd(1, 0, n - 1, ll[i], rr[i], t);
}
get(1, 0, n - 1, {-INF, INF});
}
