#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include "wall.h"
using namespace std;
const int MAX_POS = 2e6;
const int TAILLE_MAX = 1e5 + 1;
const int MAX_NOEUD = 1 << 22;
const int MID = 1 << 21;
const int RACINE = 1;
pair<int, int> lazy[MAX_NOEUD];
int hauteursFinales[MAX_POS];
void propage(int noeud)
{
for(int nxtNoeud = noeud * 2; nxtNoeud <= noeud * 2 + 1; nxtNoeud++)
{
lazy[nxtNoeud].first = max(lazy[nxtNoeud].first, lazy[noeud].first);
lazy[nxtNoeud].first = min(lazy[nxtNoeud].first, lazy[noeud].second);
lazy[nxtNoeud].second = min(lazy[nxtNoeud].second, lazy[noeud].second);
lazy[nxtNoeud].second = max(lazy[nxtNoeud].second, lazy[noeud].first);
}
lazy[noeud].first = 0;
lazy[noeud].second = MAX_POS;
}
void update(int noeud, int curDeb, int curFin, int deb, int fin, int tp, int val)
{
if(curDeb > fin || curFin < deb)
{
return;
}
if(curDeb >= deb && curFin <= fin)
{
if(tp == 1)
{
lazy[noeud].first = max(lazy[noeud].first, val);
lazy[noeud].second = max(lazy[noeud].second, val);
}
else
{
lazy[noeud].second = min(lazy[noeud].second, val);
lazy[noeud].first = min(lazy[noeud].first, val);
}
return;
}
if(curDeb == curFin)
{
return;
}
propage(noeud);
int mid = (curDeb + curFin) / 2;
update(noeud * 2, curDeb, mid, deb, fin, tp, val);
update(noeud * 2 + 1, mid + 1, curFin, deb, fin, tp, val);
}
void get_Hauteurs_Finales(int noeud, int deb, int fin, int n, int maxi)
{
//cout << noeud << " " << deb << " " << fin << " " << lazy[noeud].first << " " << lazy[noeud].second << endl;
if(lazy[noeud].first <= lazy[noeud].second)
{
maxi = max(maxi, lazy[noeud].first);
}
if(deb == fin || deb > n)
{
if(deb < n)
{
hauteursFinales[deb] = maxi;
}
return;
}
propage(noeud);
int mid = (deb + fin) / 2;
get_Hauteurs_Finales(noeud * 2, deb, mid, n, maxi);
get_Hauteurs_Finales(noeud * 2 + 1, mid + 1, fin, n, maxi);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i = 0; i < MAX_NOEUD; i++)
{
lazy[i].first = 0;
lazy[i].second = MAX_POS;
}
for(int i = 0; i < k; i++)
{
update(1, 0, MID - 1, left[i], right[i], op[i], height[i]);
}
get_Hauteurs_Finales(1, 0, MID - 1, n, 0);
for(int i = 0; i < n; i++)
{
finalHeight[i] = hauteursFinales[i];
}
}
