#include "wall.h"
#include <iostream>
using namespace std;
const int INFINI = 1000 * 1000 * 1000;
pair<int, int> bornes[(1 << 22)];
void push(pair<int, int>& init, pair<int, int> modif) {
init.first = max(init.first, modif.first);
init.second = max(init.second, init.first);
init.second = min(init.second, modif.second);
init.first = min(init.second, init.first);
}
void update(int noeud) {
if(noeud >= (1 << 21)) {
return;
}
push(bornes[2 * noeud], bornes[noeud]);
push(bornes[2 * noeud + 1], bornes[noeud]);
bornes[noeud] = {0, INFINI};
}
void update(int deb, int fin, pair<int, int> borne, int n = 1, int d = 0, int f = (1 << 21)) {
update(n);
if(deb >= f || d >= fin)
return;
if(deb <= d && f <= fin) {
push(bornes[n], borne);
update(n);
return;
}
int m = (d + f) / 2;
update(deb, fin, borne, 2 * n, d, m);
update(deb, fin, borne, 2 * n + 1, m, f);
}
void buildWall(int nbSlots, int nbReqs, int op[], int left[], int right[], int height[], int finalHeight[]) {
for(int iReq = 0;iReq < nbReqs;iReq++) {
if(op[iReq] == 1) {
update(left[iReq], right[iReq] + 1, {height[iReq], INFINI});
}
else {
update(left[iReq], right[iReq] + 1, {0, height[iReq]});
}
}
for(int iSommet = 1;iSommet < (1 << 21);iSommet++)
update(iSommet);
for(int iSommet = (1 << 21);iSommet < (1 << 21) + nbSlots;iSommet++) {
finalHeight[iSommet - (1 << 21)] = bornes[iSommet].first;
}
}
