#include "wall.h"
#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
const int N = (1 << 22), OO = 1e9;
struct Noeud {
int valMin, valMax;
};
Noeud arbre[N * 2];
void push(int noeud){
for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; ++enfant){
chmin(arbre[enfant].valMin, arbre[noeud].valMax);
chmin(arbre[enfant].valMax, arbre[noeud].valMax);
chmax(arbre[enfant].valMin, arbre[noeud].valMin);
chmax(arbre[enfant].valMax, arbre[noeud].valMin);
}
arbre[noeud] = {0, OO};
}
void update(int noeud, int curl, int curr, int reql, int reqr, int typeOp, int val){
if (curl > reqr || reql > curr)
return;
if (reql <= curl && curr <= reqr){
if (typeOp == 2){
chmin(arbre[noeud].valMin, val);
chmin(arbre[noeud].valMax, val);
}
else {
chmax(arbre[noeud].valMin, val);
chmax(arbre[noeud].valMax, val);
}
return;
}
push(noeud);
int mid = (curl + curr)/2;
update(noeud * 2, curl, mid, reql, reqr, typeOp, val);
update(noeud * 2 + 1, mid + 1, curr, reql, reqr, typeOp, val);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int noeud = 1; noeud < 2 * N; ++noeud)
arbre[noeud] = {0, OO};
for (int iReq = 0; iReq < k; ++iReq)
update(1, 0, N - 1, left[iReq], right[iReq], op[iReq], height[iReq]);
for (int ind = 0; ind < n; ++ind){
update(1, 0, N - 1, ind, ind, 2, OO);
finalHeight[ind] = arbre[N + ind].valMin;
}
}
