#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6;
int seg[4 * N], seg2[4 * N], n;
void pull (int idx, int d, int u) {
seg[idx] = min(seg[idx], d);
seg[idx] = max(seg[idx], u);
seg2[idx] = max(seg2[idx], u);
seg2[idx] = min(seg2[idx], d);
}
void push_down (int idx) {
pull(2 * idx, seg[idx], seg2[idx]);
pull(2 * idx + 1, seg[idx], seg2[idx]);
seg[idx] = 1e9;
seg2[idx] = 0;
}
#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 ? 1e9 : h, t == 1 ? h : 0);
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 < k; ++i) {
update(left[i], right[i], height[i], op[i]);
}
query(1, 0, n - 1, finalHeight);
}
