#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6;
int seg[4 * N], lazyR[4 * N], lazyA[4 * N], lazyL[4 * N], n;
void pull (int idx, int a, int r, int l) {
if (l == 1) {
seg[idx] = min(seg[idx], r);
seg[idx] = max(seg[idx], a);
}
else {
seg[idx] = max(seg[idx], a);
seg[idx] = min(seg[idx], r);
}
lazyL[idx] = l;
lazyA[idx] = max(lazyA[idx], a);
lazyR[idx] = min(lazyR[idx], r);
}
void push_down (int idx) {
if (lazyL[idx]) {
pull(2 * idx, lazyA[idx], lazyR[idx], lazyL[idx]);
pull(2 * idx + 1, lazyA[idx], lazyR[idx], lazyL[idx]);
lazyL[idx] = 0;
lazyA[idx] = -1;
lazyR[idx] = 2e9;
}
}
#define mid (L + R) / 2
void update (int st, int en, int h, int t, int idx = 1, int L = 0, int R = n - 1) {
if (L > en || R < st) {
return;
}
if (L >= st && R <= en) {
pull(idx, t == 1 ? h : -1, t == 1 ? 2e9 : h, t);
return;
}
push_down(idx);
update(st, en, h, t, 2 * idx, L, mid);
update(st, en, h, t, 2 * idx + 1, mid + 1, R);
}
void query (int idx, int L, int R, int f[]) {
if (L == R) {
f[L] = seg[idx];
return;
}
push_down(idx);
query(2 * idx, L, mid, f);
query(2 * idx + 1, mid + 1, R, f);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
::n = n;
for (int i = 0; i < 4 * N; ++i) {
lazyA[i] = -1;
lazyR[i] = 2e9;
}
for (int i = 0; i < k; ++i) {
update(left[i], right[i], height[i], op[i]);
}
query(1, 0, n - 1, finalHeight);
}
