#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int seg1[8000005], seg2[8000005]; // min, max
int inf = 1e9;
int mn[2000005], mx[2000005];
void push(int x, int l, int r) {
if(l==r) return;
seg1[x*2] = min(seg1[x*2], seg1[x]);
seg2[x*2] = min(seg2[x*2], seg1[x]);
seg1[x*2] = max(seg1[x*2], seg2[x]);
seg2[x*2] = max(seg2[x*2], seg2[x]);
seg1[x*2+1] = min(seg1[x*2+1], seg1[x]);
seg2[x*2+1] = min(seg2[x*2+1], seg1[x]);
seg1[x*2+1] = max(seg1[x*2+1], seg2[x]);
seg2[x*2+1] = max(seg2[x*2+1], seg2[x]);
seg1[x] = inf; seg2[x] = -inf;
}
void upd(int x, int l, int r, int ll, int rr, int tp, int val) {
if(l > rr || r < ll) return;
push(x, l, r);
if(ll <= l && r <= rr) {
if(tp==1) { // max operation
seg1[x] = max(seg1[x], val);
seg2[x] = max(seg2[x], val);
} else {
seg1[x] = min(seg1[x], val);
seg2[x] = min(seg2[x], val);
}
} else {
upd(x*2, l, (l+r)/2, ll, rr, tp, val);
upd(x*2+1, (l+r)/2+1, r, ll, rr, tp, val);
}
}
void qry(int x, int l, int r) {
push(x, l, r);
if(l==r) {
mn[l] = seg1[x];
mx[l] = seg2[x];
} else {
qry(x*2, l, (l+r)/2);
qry(x*2+1, (l+r)/2+1, r);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(seg1, inf, sizeof(seg1));
memset(seg2, -inf, sizeof(seg2));
for(int i=0; i<k; i++) {
upd(1, 0, n-1, left[i], right[i], op[i], height[i]);
}
qry(1, 0, n-1);
for(int i=0; i<n; i++) {
finalHeight[i] = max(min(0, mn[i]), mx[i]);
}
}
