#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e6+10;
const int INF = 1e9;
int segVal[MAXN], lazyMax[MAXN], lazyMin[MAXN];
int iDeb[MAXN], iFin[MAXN];
void buildTree(int iNoeud, int li, int ri)
{
iDeb[iNoeud] = li, iFin[iNoeud] = ri;
lazyMax[iNoeud] = 0;
lazyMin[iNoeud] = INF;
if (li == ri)
return;
buildTree(2*iNoeud, li, (li+ri)/2);
buildTree(2*iNoeud+1, (li+ri)/2+1, ri);
}
void changeMax(int iNoeud, int val)
{
lazyMax[iNoeud] = max(lazyMax[iNoeud], val);
lazyMin[iNoeud] = max(lazyMin[iNoeud], val);
}
void changeMin(int iNoeud, int val)
{
lazyMin[iNoeud] = min(lazyMin[iNoeud], val);
lazyMax[iNoeud] = min(lazyMax[iNoeud], val);
}
void pushDown(int iNoeud)
{
segVal[iNoeud] = max(segVal[iNoeud], lazyMax[iNoeud]);
segVal[iNoeud] = min(segVal[iNoeud], lazyMin[iNoeud]);
if (iDeb[iNoeud] < iFin[iNoeud])
{
changeMax(2*iNoeud, lazyMax[iNoeud]);
changeMin(2*iNoeud, lazyMin[iNoeud]);
changeMax(2*iNoeud+1, lazyMax[iNoeud]);
changeMin(2*iNoeud+1, lazyMin[iNoeud]);
}
lazyMax[iNoeud] = 0, lazyMin[iNoeud] = INF;
}
int getVal(int iNoeud, int pos)
{
pushDown(iNoeud);
if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos) return 0;
if (iDeb[iNoeud] == iFin[iNoeud])
return segVal[iNoeud];
return getVal(2*iNoeud, pos) + getVal(2*iNoeud+1, pos);
}
void update(int iNoeud, int deb, int fin, int op, int val)
{
pushDown(iNoeud);
if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
return;
if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin)
{
if (op==1)
lazyMax[iNoeud] = val;
else
lazyMin[iNoeud] = val;
pushDown(iNoeud);
return ;
}
update(2*iNoeud, deb, fin, op, val);
update(2*iNoeud+1, deb, fin, op, val);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
buildTree(1, 0, n-1);
for (int i(0); i < k; ++i)
update(1, left[i], right[i], op[i], height[i]);
for (int i(0); i < n; ++i)
finalHeight[i] = getVal(1, i);
return;
}
