#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct Op {
int lo = 0, hi = 1e9;
};
struct Seg {
vector<Op> lazy;
int n;
Seg(int sz) {
n = sz;
lazy = vector<Op>(4*n);
}
void apply(int id, Op op) {
lazy[id].lo = min(max(lazy[id].lo, op.lo), op.hi);
lazy[id].hi = min(max(lazy[id].hi, op.lo), op.hi);
}
void push(int id) {
apply(2*id, lazy[id]);
apply(2*id+1, lazy[id]);
lazy[id] = Op{};
}
void update(int id, int x, int y, int l, int r, Op op) {
if (x >= r || l >= y) return;
if (x <= l && r <= y) { apply(id, op); return; }
push(id);
int m = (l+r)/2;
update(id*2, x, y, l, m, op);
update(id*2+1, x, y, m, r, op);
}
ll query(int id, int x, int y, int l, int r) {
if (x >= r || l >= y) return 0;
if (x <= l && r <= y) return lazy[id].lo;
push(id);
int m = (l+r)/2;
return max(query(id*2, x, y, l, m), query(id*2+1, x, y, m, r));
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
Seg t(n);
for (int i = 0; i < k; i++) {
t.update(1, left[i], right[i]+1, 0, n, Op{op[i] == 1 ? height[i] : 0, op[i] == 1 ? (int)1e9 : height[i]});
//for (int j = 0; j < n; j++) cout << t.query(1, j, j+1, 0, n) << " "; cout << endl;
}
for (int i = 0; i < n; i++) finalHeight[i] = t.query(1, i, i+1, 0, n);
}
