#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(int i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
const int INF = 1e9+7;
int N;
vector<int> tree;
vector<pair<int,int>> lazy;
void pushdown(int tl, int tr, int i) {
if (lazy[i].F != -INF) {
if (tree[i] < lazy[i].F && lazy[i].S == 1) tree[i] = lazy[i].F; // add
if (tree[i] > lazy[i].F && lazy[i].S == 2) tree[i] = lazy[i].F; // remove
if (tl != tr) {
lazy[i*2] = lazy[i];
lazy[i*2+1] = lazy[i];
}
lazy[i] = {-INF,-INF};
}
}
void update(pair<int,int> v, int l, int r, int tl = 0, int tr = N-1, int i = 1) {
pushdown(tl, tr, i);
if (l > r) return;
if (tl == l && tr == r) {
lazy[i] = v;
pushdown(tl, tr, i);
return;
}
int tm = (tl + tr) / 2;
update(v, l, min(r, tm), tl, tm, i * 2);
update(v, max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
int query(int l, int r, int tl = 0, int tr = N-1, int i = 1) {
pushdown(tl, tr, i);
if (l > r) return -INF;
if (tl == l && tr == r) return tree[i];
int tm = (tl + tr) / 2;
return max(query(l, min(r, tm), tl, tm, i * 2), query(max(l, tm + 1), r, tm + 1, tr, i * 2 + 1));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
N = n;
tree.resize(4*N);
lazy.resize(4*N, {-INF, -INF});
FOR(i,k) {
update({height[i], op[i]}, left[i], right[i]);
}
FOR(i,n) {
finalHeight[i] = query(i,i);
}
}
