#include "wall.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2'000'002;
int add[4 * maxn], sub[4 * maxn];
void Comp(int v, int h, int t)
{
if (h == -1) return;
if (add[v] == -1 && sub[v] == -1)
{
if (t == 1) add[v] = h;
else sub[v] = h;
return;
}
if (t == 1 && add[v] != -1)
{
add[v] = max(add[v], h);
if (sub[v] != -1 && sub[v] < add[v])
sub[v] = add[v];
return;
}
if (t == 2 && sub[v] != -1)
{
sub[v] = min(sub[v], h);
if (add[v] != -1 && sub[v] < add[v])
add[v] = sub[v];
return;
}
if (t == 1)
{
if (h >= sub[v])
{
sub[v] = add[v] = h;
return;
}
add[v] = h;
return;
}
if (h <= add[v])
{
sub[v] = add[v] = h;
return;
}
sub[v] = h;
return;
}
void Push(int v)
{
Comp(v * 2, add[v], 1);
Comp(v * 2, sub[v], 2);
Comp(v * 2 + 1, add[v], 1);
Comp(v * 2 + 1, sub[v], 2);
add[v] = sub[v] = -1;
}
void Upd(int v, int vl, int vr, int l, int r, int h, int t)
{
if (r < l) return;
if (vl == l && vr == r)
{
Comp(v, h, t);
return;
}
int m = (vl + vr) / 2;
Push(v);
Upd(v * 2, vl, m, l, min(m, r), h, t);
Upd(v * 2 + 1, m + 1, vr, max(l, m + 1), r, h, t);
}
pair<int, int> Get(int v, int vl, int vr, int pos)
{
if (vl == vr)
return {add[v], sub[v]};
int m = (vl + vr) / 2;
Push(v);
if (pos <= m)
return Get(v * 2, vl, m, pos);
else return Get(v * 2 + 1, m + 1, vr, pos);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < 4 * maxn; i++)
sub[i] = add[i] = -1;
for (int i = 0; i < k; i++)
Upd(1, 0, n - 1, left[i], right[i], height[i], op[i]);
fill(finalHeight, finalHeight + n, 0);
for (int i = 0; i < n; i++)
{
auto x = Get(1, 0, n - 1, i);
if (x.first == -1 && x.second == -1)
continue;
if (x.first != -1 && x.second != -1)
{
if (finalHeight[i] <= x.first)
finalHeight[i] = x.first;
else finalHeight[i] = x.second;
continue;
}
if (x.first != -1 && finalHeight[i] <= x.first)
finalHeight[i] = x.first;
if (x.second != -1 && finalHeight[i] > x.second)
finalHeight[i] = x.second;
}
return;
}
