#include <iostream>
#include <cstdio>
#include "wall.h"
using namespace std;
const int INFINI = (1000 * 1000 * 1000);
const int TAILLE_ARBRE = (1 << 21);
pair <int, int> Tree[2 * TAILLE_ARBRE];
void Push(int noeud) {
if (noeud >= TAILLE_ARBRE)
return;
for (int d = 0; d < 2; d ++)
{
Tree[2 * noeud + d] = {max(Tree[2 * noeud + d].first, Tree[noeud].first), min(Tree[2 * noeud + d].second, Tree[noeud].second)};
Tree[2 * noeud + d] = {min(Tree[2 * noeud + d].first, Tree[noeud].second), max(Tree[2 * noeud + d].second, Tree[noeud].first)};
}
Tree[noeud] = {0, INFINI};
return;
}
void AddNew(int noeud, int gauche, int droite, int inf, int sup, pair <int, int> update) {
if (gauche >= sup || droite <= inf)
return;
Push(noeud);
if (inf <= gauche && droite <= sup)
{
if (noeud < TAILLE_ARBRE)
Tree[noeud] = update;
else
Tree[noeud].first = Tree[noeud].second = min(max(Tree[noeud].first, update.first), update.second);
return;
}
int mid = (gauche + droite) / 2;
AddNew(2 * noeud, gauche, mid, inf, sup, update);
AddNew(2 * noeud + 1, mid, droite, inf, sup, update);
return;
}
void buildWall(int nbColonnes, int nbOperations, int TypeOp[], int Left[], int Right[], int Hauteur[], int Ans[]){
for (int i = 0; i < nbOperations; i ++)
{
if (TypeOp[i] == 1)
AddNew(1, 0, TAILLE_ARBRE, Left[i], Right[i] + 1, {Hauteur[i], INFINI});
else
AddNew(1, 0, TAILLE_ARBRE, Left[i], Right[i] + 1, {0, Hauteur[i]});
}
for (int i = 1; i < TAILLE_ARBRE; i ++)
{
Push(i);
}
for (int i = 0; i < nbColonnes; i ++)
{
Ans[i] = Tree[i + TAILLE_ARBRE].first;
}
return;
}
