#include "bits/stdc++.h"
#include "wall.h"
// #include "grader.cpp"
using namespace std;
#define N 500005
int D[N], U[N], finalH[N];
void combine(int l,int r,int ind) {
if(l == r) return;
D[ind * 2] = min(D[ind * 2], D[ind]);
D[ind * 2] = max(D[ind * 2], U[ind]);
U[ind * 2] = min(U[ind * 2], D[ind]);
U[ind * 2] = max(U[ind * 2], U[ind]);
D[ind * 2 + 1] = min(D[ind * 2 + 1], D[ind]);
D[ind * 2 + 1] = max(D[ind * 2 + 1], U[ind]);
U[ind * 2 + 1] = min(U[ind * 2 + 1], D[ind]);
U[ind * 2 + 1] = max(U[ind * 2 + 1], U[ind]);
U[ind] = INT_MIN;
D[ind] = INT_MAX;
return;
}
void upd(int l,int r,int ind,int tp, int x,int y,int vl) {
if(r < x || l > y) return;
combine(l, r, ind);
if(l >= x && r <= y) {
if(tp == 1){
U[ind] = max(U[ind], vl);
D[ind] = max(D[ind], vl);
}
else {
U[ind] = min(U[ind], vl);
D[ind] = min(D[ind], vl);
}
return;
}
int mid = (l + r) / 2;
upd(l, mid, ind * 2, tp, x, y, vl);
upd(mid + 1, r, ind * 2 + 1, tp, x, y, vl);
}
void build(int l,int r,int ind) {
if(l == r) {
// cout << l << " " << U[ind] << " " << D[ind] << '\n';
finalH[l] = min(U[ind], D[ind]);
return;
}
combine(l, r, ind);
int mid = (l + r) / 2;
build(l,mid,ind*2);
build(mid+1,r,ind*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; i++) {
upd(1, n, 1, op[i], left[i] + 1, right[i] + 1, height[i]);
}
build(1, n, 1);
for(int i = 0; i < n; i++) {
finalHeight[i] = finalH[i + 1];
}
return;
}
