#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 2000000;
int arbre[NMAX*3+1];
pair<int, int> debFin[NMAX*3+1];
int aPush[NMAX*3+1][2];
int hFin[NMAX];
#define INFINI 2000000
void tester(int noeud, int deb, int fin)
{
// cout << noeud << " : " << deb << " " << fin << endl;
aPush[noeud][0] = 0;
aPush[noeud][1] = INFINI;
debFin[noeud] = {deb, fin};
if(deb == fin-1) return;
tester(noeud*2, deb, (deb+fin)/2);
tester(noeud*2+1, (deb+fin)/2, fin);
}
void chang(int noeud)
{
if(debFin[noeud].first == debFin[noeud].second-1)
{
hFin[debFin[noeud].first] = max(aPush[noeud][0], hFin[debFin[noeud].first]);
hFin[debFin[noeud].first] = min(aPush[noeud][1], hFin[debFin[noeud].first]);
//cout << "dhkjd" << noeud << endl;
}
else
{
if(aPush[noeud][0] > aPush[noeud*2][1])
{
aPush[noeud*2][1] = aPush[noeud][0];
}
if(aPush[noeud][1] < aPush[noeud*2][0])
{
aPush[noeud*2][0] = aPush[noeud][1];
}
aPush[noeud*2][0] = max(aPush[noeud][0], aPush[noeud*2][0]);
aPush[noeud*2][1] = min(aPush[noeud][1], aPush[noeud*2][1]);
if(aPush[noeud][0] > aPush[noeud*2+1][1])
{
aPush[noeud*2+1][1] = aPush[noeud][0];
}
if(aPush[noeud][1] < aPush[noeud*2+1][0])
{
aPush[noeud*2+1][0] = aPush[noeud][1];
}
aPush[noeud*2+1][0] = max(aPush[noeud][0], aPush[noeud*2+1][0]);
aPush[noeud*2+1][1] = min(aPush[noeud][1], aPush[noeud*2+1][1]);
}
aPush[noeud][0] = 0;
aPush[noeud][1] = INFINI;
}
void testerFin(int noeud, int deb, int fin)
{
chang(noeud);
// cout << noeud << " : " << deb << " " << fin << endl;
if(deb == fin-1) return;
testerFin(noeud*2, deb, (deb+fin)/2);
testerFin(noeud*2+1, (deb+fin)/2, fin);
}
void adapter(int noeud, int deb, int fin, int op, int h)
{
chang(noeud);
if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return;
// cout << noeud << endl;
if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))
{
if(op == 0)
{
aPush[noeud][0] = max(aPush[noeud][0], h);
if(aPush[noeud][1] < h)
{
aPush[noeud][1] = h;
}
}
else
{
aPush[noeud][1] = min(aPush[noeud][1], h);
if(aPush[noeud][0] > h)
{
aPush[noeud][0] = h;
}
}
return;
}
adapter(noeud*2, deb, fin, op, h);
adapter(noeud*2+1, deb, fin, op, h);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
tester(1, 0, n);
for(int i = 0; i < k; i++)
{
int opADonner = op[i]-1;
int debADonner = left[i];
int finADonner = right[i]+1;
int hADonner = height[i];
adapter(1, debADonner, finADonner, opADonner, hADonner);
/* for(int i = 1; i < 32; i++)
{
cout << i << " : ";
cout << aPush[i][0] << " " << aPush[i][1] << "\n";
}
cout << endl;/** */
}
testerFin(1, 0, n);
for(int i = 0; i < n; i++)
{
finalHeight[i] = hFin[i];
}
return;
}
