#include <bits/stdc++.h>
typedef long long ll;
const long long inf = 2e9;
using namespace std;
struct Node
{
Node *l = 0, *r = 0;
int lo, hi;
int max_of_interval = inf, min_of_interval = -inf; // Allowed max and allowed min of intervals
Node(int lo, int hi) : lo(lo), hi(hi)
{
if (lo + 1 < hi)
{
int mid = lo + (hi - lo) / 2;
l = new Node(lo, mid);
r = new Node(mid, hi);
}
}
~Node()
{
delete l;
delete r;
}
int query(int pos)
{
if (lo + 1 == hi)
return min_of_interval == -inf ? 0 : min_of_interval;
push();
int mid = lo + (hi - lo) / 2;
if (pos < mid)
return l->query(pos);
return r->query(pos);
}
void minimize(int L, int R, int X)
{
if (R <= lo || hi <= L)
return;
if (L <= lo && hi <= R)
{
max_of_interval = min(X, max_of_interval);
min_of_interval = min(X, min_of_interval);
return;
}
push();
l->minimize(L, R, X);
r->minimize(L, R, X);
}
void maximize(int L, int R, int X)
{
if (R <= lo || hi <= L)
return;
if (L <= lo && hi <= R)
{
min_of_interval = max(X, min_of_interval);
max_of_interval = max(max_of_interval, min_of_interval);
return;
}
push();
l->maximize(L, R, X);
r->maximize(L, R, X);
}
void push()
{
l->minimize(lo, hi, max_of_interval);
r->minimize(lo, hi, max_of_interval);
l->maximize(lo, hi, min_of_interval);
r->maximize(lo, hi, min_of_interval);
max_of_interval=inf;
min_of_interval=-inf;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
Node *tree = new Node(0, n);
for (int i = 0; i < k; i++)
{
ll l, r, a, type;
type = op[i];
l = left[i];
r = right[i];
a = height[i];
r++;
type--;
if (type)
tree->minimize(l, r, a);
else
tree->maximize(l, r, a);
}
for (int i = 0; i < n; i++)
{
finalHeight[i] = tree->query(i);
}
delete tree;
}
