#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
int mn;
int mx;
node(){
mn = 1e9;
mx = -1e9;
}
};
const int N = 2e6 + 3e2;
node t[4 * N];
void chmin(node &var, int val){
var.mn = min(var.mn, val);
var.mx = min(var.mx, val);
}
void chmax(node &var, int val){
var.mn = max(var.mn, val);
var.mx = max(var.mx, val);
}
void push(int v){
if (t[v].mn != 1e9){
chmin(t[v + v], t[v].mn);
chmin(t[v + v + 1], t[v].mn);
t[v].mn = 1e9;
}
if (t[v].mx != -1e9){
chmax(t[v + v], t[v].mx);
chmax(t[v + v + 1], t[v].mx);
t[v].mx = -1e9;
}
}
void update(int v, int tl, int tr, int l, int r, int val, char type){
if (l <= tl && tr <= r){
if (type == '+'){
chmax(t[v], val);
} else {
chmin(t[v], val);
}
return;
}
if (tl > r || tr < l) return;
push(v);
int tm = (tl + tr) >> 1;
update(v + v, tl, tm, l, r, val, type);
update(v + v + 1, tm + 1, tr, l, r, val, type);
}
node get(int v, int tl, int tr, int pos){
if (tl == tr) return t[v];
push(v);
int tm = (tl + tr) >> 1;
if (pos <= tm) return get(v + v, tl, tm, pos); else
return get(v + v + 1, tm + 1, tr, pos);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < n; i++){
update(1, 0, n - 1, i, i, 0, '+');
}
for (int i = 0; i < k; i++){
update(1, 0, n - 1, left[i], right[i], height[i], op[i] == 1 ? '+' : '-');
}
for (int i = 0; i < n; i++){
finalHeight[i] = get(1, 0, n - 1, i).mx;
}
}
