#include <bits/stdc++.h>
#include "wall.h"
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(s) (int)s.size()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
const int N = (1 << 21), OO = INT_MAX;
struct Noeud {
int bornes[2];
};
Noeud arbre[N * 2];
void init(){
for (int noeud = 1; noeud < 2 * N; ++noeud){
arbre[noeud].bornes[0] = 0;
arbre[noeud].bornes[1] = OO;
}
}
void prop(int noeud){
for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; ++enfant){
for (int iBorne = 0; iBorne < 2; ++iBorne){
chmin(arbre[enfant].bornes[iBorne], arbre[noeud].bornes[1]);
chmax(arbre[enfant].bornes[iBorne], arbre[noeud].bornes[0]);
}
}
}
void add(int noeud, int curl, int curr, int reql, int reqr, int typeReq, int val){
if (curl > reqr || reql > curr)
return;
if (reql <= curl && curr <= reqr){
for (int iBorne = 0; iBorne < 2; ++iBorne){
if (typeReq == 2)
chmin(arbre[noeud].bornes[iBorne], val);
else
chmax(arbre[noeud].bornes[iBorne], val);
// cout << "REQ " << arbre[noeud].bornes[0] << " " << arbre[noeud].bornes[1] << endl;
}
return;
}
int mid = (curl + curr)/2;
prop(noeud);
add(noeud * 2, curl, mid, reql, reqr, typeReq, val);
add(noeud * 2 + 1, mid + 1, curr, reql, reqr, typeReq, val);
}
void toutPropager(int indice){
add(1, 0, N - 1, indice, indice, 1, 0);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
init();
int nVals = n, nReqs = k;
for (int iReq = 0; iReq < nReqs; ++iReq){
//left[iReq]++; right[iReq]++;
add(1, 0, N - 1, left[iReq], right[iReq], op[iReq], height[iReq]);
}
for (int iVal = 0; iVal < nVals; ++iVal){
toutPropager(iVal);
finalHeight[iVal] = arbre[N + iVal].bornes[0];
//cout << arbre[N + iVal].bornes[0] << " " << arbre[N + iVal].bornes[1] << endl;
}
return;
}
