#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
const int M = 1000000000;
int tree[4 * N][2];
void apply(int node, array<int, 2>& make)
{
if (tree[node][0] <= make[0])
{
tree[node][0] = max(make[0], tree[node][0]);
tree[node][1] = max(min(make[1], tree[node][1]), tree[node][0]);
} else
{
tree[node][1] = min(make[1], tree[node][1]);
tree[node][0] = min(max(make[0], tree[node][0]), tree[node][1]);
}
}
void push(int node)
{
array<int, 2> temp = {tree[node][0], tree[node][1]};
for (int i = 0; i <= 1; i++) apply(node * 2 + i, temp);
tree[node][0] = -1;
tree[node][1] = M;
}
void ins(int from, int to, array<int, 2>& make, int a, int b, int node)
{
if (from <= a && b <= to)
{
apply(node, make);
return;
}
int mid = (a + b) / 2;
push(node);
if (from <= mid) ins(from, to, make, a, mid, node * 2);
if (to > mid) ins(from, to, make, mid + 1, b, node * 2 +1);
}
int getRes(int i, int a, int b, int node)
{
if (a == b) return tree[node][0];
int mid = (a + b) / 2;
push(node);
if (i <= mid) return getRes(i, a, mid, node * 2);
return getRes(i, mid + 1, b, node * 2 + 1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; i++)
{
int a = left[i];
int b = right[i];
array<int, 2> make = {};
make[0] = -1;
make[1] = M;
if (op[i] == 1)
{
make[0] = height[i];
} else make[1] = height[i];
ins(a, b, make, 0, n - 1, 1);
}
for (int i = 0; i < n; i++) finalHeight[i] = getRes(i, 0, n - 1, 1);
}
