#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
const int N = 2e6 + 3;
const int inf = 1e9;
struct node {
int opmax, opmin;
};
struct segtree {
vector<node> op;
int size_s = 1;
void init(int n) {
while (size_s <= n) size_s *= 2;
op.assign(4*N, {0, inf});
}
void propagate(int x, int lx, int rx) {
if (rx - lx == 1) return;
op[x*2+1] = {min(op[x].opmin, max(op[x*2+1].opmax, op[x].opmax)), max(op[x].opmax, min(op[x*2+1].opmin, op[x].opmin))};
op[x*2+2] = {min(op[x].opmin, max(op[x*2+2].opmax, op[x].opmax)), max(op[x].opmax, min(op[x*2+2].opmin, op[x].opmin))};
op[x] = {0, inf};
}
void minimum(int x, int lx, int rx, int l, int r, int v) {
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
op[x].opmin = min(op[x].opmin, v);
op[x].opmax = min(op[x].opmax, v);
return;
}
propagate(x, lx, rx);
int m = (lx + rx) / 2;
minimum(x * 2 + 1, lx, m, l, r, v);
minimum(x * 2 + 2, m, rx, l, r, v);
}
void minimum(int l, int r, int v) {
minimum(0, 0, N, l, r+1, v);
}
void maksimum(int x, int lx, int rx, int l, int r, int v) {
//dbg(size_s, lx, rx, l, r);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
op[x].opmin = max(op[x].opmin, v);
op[x].opmax = max(op[x].opmax, v);
return;
}
propagate(x, lx, rx);
int m = (lx + rx) / 2;
maksimum(x * 2 + 1, lx, m, l, r, v);
maksimum(x * 2 + 2, m, rx, l, r, v);
}
void maksimum(int l, int r, int v) {
maksimum(0, 0, N, l, r+1, v);
}
int get(int x, int lx, int rx, int i) {
if (rx - lx == 1)
return op[x].opmax;
propagate(x, lx, rx);
int m = (lx + rx) / 2;
if (i < m)
return get(x * 2 + 1, lx, m, i);
else
return get(x * 2 + 2, m, rx, i);
}
int get(int i) {
return get(0, 0, N, i);
}
}; segtree seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
seg.init(n);
for (int i = 0; i < k; i++) {
int l = left[i], r = right[i], h = height[i];
if (op[i] == 1)
seg.maksimum(l, r, h);
else
seg.minimum(l, r, h);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = seg.get(i);
}
}
