#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct info {
int l, r;
};
const int MAX_N = 2e6;
const int INF = 1e5;
info lazy[4 * MAX_N];
void propag(int v, int l, int r) {
if (l == r)
return;
lazy[v * 2 + 1].l = min(lazy[v * 2 + 1].l, lazy[v].r);
lazy[v * 2 + 1].l = max(lazy[v * 2 + 1].l, lazy[v].l);
lazy[v * 2 + 1].r = min(lazy[v * 2 + 1].r, lazy[v].r);
lazy[v * 2 + 1].r = max(lazy[v * 2 + 1].r, lazy[v].l);
lazy[v * 2 + 2].l = min(lazy[v * 2 + 2].l, lazy[v].r);
lazy[v * 2 + 2].l = max(lazy[v * 2 + 2].l, lazy[v].l);
lazy[v * 2 + 2].r = min(lazy[v * 2 + 2].r, lazy[v].r);
lazy[v * 2 + 2].r = max(lazy[v * 2 + 2].r, lazy[v].l);
lazy[v] = {0, INF};
}
int timee = 0;
void update(int v, int l, int r, int lu, int ru, int t, int k) {
propag(v, l, r);
if (l > ru || r < lu)
return;
if (lu <= l && r <= ru) {
if (t == 1) {
lazy[v].l = max(lazy[v].l, k);
lazy[v].r = max(lazy[v].r, k);
} else {
lazy[v].l = min(lazy[v].l, k);
lazy[v].r = min(lazy[v].r, k);
}
propag(v, l, r);
return;
}
int mid = (l + r) / 2;
update(v * 2 + 1, l, mid, lu, ru, t, k);
update(v * 2 + 2, mid + 1, r, lu, ru, t, k);
}
void getFinalHeight(int v, int l, int r, int finalHeight[]) {
propag(v, l, r);
// printf("%d %d -> %d %d\n", l, r, lazy[v].l, lazy[v].r);
if (l == r) {
finalHeight[l] = lazy[v].l;
return;
}
int mid = (l + r) / 2;
getFinalHeight(v * 2 + 1, l, mid, finalHeight);
getFinalHeight(v * 2 + 2, mid + 1, r, finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int v = 0; v < 4 * n; v++)
lazy[v] = {0, INF};
for (int i = 0; i < k; i++)
update(0, 0, n - 1, left[i], right[i], op[i], height[i]);
getFinalHeight(0, 0, n - 1, finalHeight);
}
