#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree
{
vector<long> lower, upper;
size_t l;
segtree(size_t n)
{
l = 1 << (32 - __builtin_clz(n));
lower = vector<long>(2 * l, 0);
upper = vector<long>(2 * l, LONG_MAX);
}
void propagate(size_t k, size_t x, size_t y)
{
if (k < l)
{
upper[2 * k] = max(min(upper[k], upper[2 * k]), lower[k]);
upper[2 * k + 1] = max(min(upper[k], upper[2 * k + 1]), lower[k]);
lower[2 * k] = min(max(lower[k], lower[2 * k]), upper[k]);
lower[2 * k + 1] = min(max(lower[k], lower[2 * k + 1]), upper[k]);
}
}
void update(size_t i, size_t j, long v, bool is_lower, size_t k, size_t x, size_t y)
{
if (x > y || y < i || x > j)
return;
if (i <= x && y <= j)
{
if (is_lower)
{
lower[k] = max(lower[k], v);
upper[k] = max(upper[k], lower[k]);
}
else
{
upper[k] = min(upper[k], v);
lower[k] = min(lower[k], upper[k]);
}
}
else
{
propagate(k, x, y);
update(i, j, v, is_lower, 2 * k, x, (x + y) / 2);
update(i, j, v, is_lower, 2 * k + 1, (x + y) / 2 + 1, y);
}
}
long point_val(size_t i, size_t k, size_t x, size_t y)
{
if (x == y)
return lower[k];
propagate(k, x, y);
if (i <= (x + y) / 2)
return point_val(i, 2 * k, x, (x + y) / 2);
else
return point_val(i, 2 * k + 1, (x + y) / 2 + 1, y);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segtree tree(n);
for (size_t i = 0; i < k; i++)
tree.update(left[i], right[i], height[i], op[i] == 1, 1, 0, tree.l - 1);
for (size_t i = 0; i < n; i++)
finalHeight[i] = tree.point_val(i, 1, 0, tree.l - 1);
}
