#include <bits/stdc++.h>
#include <wall.h>
using namespace std;
const int INFINI = 200000;
int arbreBinaireMin[(1 << 18)];
int arbreBinaireMax[(1 << 18)];
void initialise() {
for (int i = 0; i < (1 << 18); i ++) {
arbreBinaireMin[i] = INFINI;
arbreBinaireMax[i] = 0;
}
}
int corr(int ind) {
return ind + (1 << 17);
}
int valMin(int ind) {
int miniCur = INFINI;
while (ind > 0) {
miniCur = min(miniCur, arbreBinaireMin[ind]);
ind /= 2;
}
return miniCur;
}
int valMax(int ind) {
int maxiCur = 0;
while (ind > 0) {
maxiCur = max(maxiCur, arbreBinaireMax[ind]);
ind /= 2;
}
return maxiCur;
}
void interMin(int L, int R, int val) {
if (L > R)
return;
if (L == R) {
arbreBinaireMin[L] = min(arbreBinaireMin[L], val);
}
if (L % 2) {
arbreBinaireMin[L] = min(arbreBinaireMin[L], val);
L ++;
}
if (! (R % 2)) {
arbreBinaireMin[R] = min(arbreBinaireMin[R], val);
R --;
}
interMin(L / 2, R / 2, val);
}
void interMax(int L, int R, int val) {
if (L > R)
return;
if (L == R) {
arbreBinaireMax[L] = max(arbreBinaireMax[L], val);
}
if (L % 2) {
arbreBinaireMax[L] = max(arbreBinaireMax[L], val);
L ++;
}
if (! (R % 2)) {
arbreBinaireMax[R] = max(arbreBinaireMax[R], val);
R --;
}
interMax(L / 2, R / 2, val);
}
void buildWall(int N, int K, int operations[], int gauche[], int droite[], int hauteur[], int hauteurFinale[]) {
for (int i = 0; i < N; i ++)
hauteurFinale[i] = 0;
if ((N <= 10000) and (K <= 5000)) {
for (int iOperation = 0; iOperation < K; iOperation ++) {
if (operations[iOperation] == 1) {
for (int indice = gauche[iOperation]; indice <= droite[iOperation]; indice ++) {
if (hauteurFinale[indice] <= hauteur[iOperation])
hauteurFinale[indice] = hauteur[iOperation];
}
}
else {
for (int indice = gauche[iOperation]; indice <= droite[iOperation]; indice ++) {
if (hauteurFinale[indice] >= hauteur[iOperation])
hauteurFinale[indice] = hauteur[iOperation];
}
}
}
return;
}
initialise();
for (int iOperation = 0; iOperation < K; iOperation ++) {
if (operations[iOperation] == 1) {
interMax(corr(gauche[iOperation]), corr(droite[iOperation]), hauteur[iOperation]);
}
else {
interMin(corr(gauche[iOperation]), corr(droite[iOperation]), hauteur[iOperation]);
}
}
for (int i = 0; i < N; i ++)
hauteurFinale[i] = min(valMax(corr(i)), valMin(corr(i)));
}
