#include "wall.h"
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define inf 1000000
using namespace std;
vector<pair<int, int>> sg(8000005, pair<int, int>(0, inf));
int a[2000005];
void propagate(int vz, int l, int d)
{
if (l == d)
return;
int lv = vz*2+1, ds = vz*2+2;
sg[lv].first = min(sg[lv].first, sg[vz].second);
sg[lv].second = min(sg[lv].second, sg[vz].second);
sg[lv].first = max(sg[lv].first, sg[vz].first);
sg[lv].second = max(sg[lv].second, sg[vz].first);
sg[ds].first = min(sg[ds].first, sg[vz].second);
sg[ds].second = min(sg[ds].second, sg[vz].second);
sg[ds].first = max(sg[ds].first, sg[vz].first);
sg[ds].second = max(sg[ds].second, sg[vz].first);
sg[vz] = {0, inf};
}
void updmn(int vz, int l, int d, int i, int j, int hg)
{
if (i > d || j < l)
return;
propagate(vz, l, d);
if (i <= l && j >= d)
{
sg[vz].first = min(sg[vz].first, hg);
sg[vz].second = min(sg[vz].second, hg);
return;
}
int mid = (l+d)/2;
updmn(vz*2+1, l, mid, i, min(mid, j), hg);
updmn(vz*2+2, mid+1, d, max(mid+1, i), j, hg);
}
void updmx(int vz, int l, int d, int i, int j, int hg)
{
if (i > d || j < l)
return;
if (i <= l && j >= d)
{
sg[vz].first = max(sg[vz].first, hg);
sg[vz].second = max(sg[vz].second, hg);
return;
}
propagate(vz, l, d);
int mid = (l+d)/2;
updmx(vz*2+1, l, mid, i, min(mid, j), hg);
updmx(vz*2+2, mid+1, d, max(mid+1, i), j, hg);
}
void izpis(int vz, int l, int d)
{
propagate(vz, l, d);
if (l == d)
{
a[l] = sg[vz].first;
return;
}
int mid = (l+d)/2;
izpis(vz*2+1, l, mid);
izpis(vz*2+2, mid+1, d);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for (int i = 0; i < k; i++)
{
int l = left[i], r = right[i];
if (op[i] == 2)
updmn(0, 0, n-1, l, r, height[i]);
else
updmx(0, 0, n-1, l, r, height[i]);
}
izpis(0, 0, n-1);
for (int i = 0; i < n; i++)
finalHeight[i] = a[i];
return;
}
