#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
class SegTree
{
private:
int N;
vector<int> A, B;
int l(int x) { return (x << 1); }
int r(int x) { return (x << 1) + 1; }
public:
SegTree(int x)
{
N = pow(2, ceil(log2(x)));
A.assign(2 * N, 0);
B.assign(2 * N, 100000);
}
void update(int X, int vala, int valb)
{
int x = X + N;
A[x] = vala, B[x] = valb;
x /= 2;
while (x)
{
B[x] = max(A[r(x)], min(B[l(x)], B[r(x)]));
A[x] = min(B[x], max(A[l(x)], A[r(x)]));
x /= 2;
}
}
int PQ() { return A[1]; }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
SegTree ST(k);
vector<vector<int>> Tab;
for (int i = 0; i < k; i++)
{
int a = 0, b = height[i];
if (op[i] == 1)
a = height[i], b = 100000;
Tab.push_back({left[i], i, a, b});
Tab.push_back({right[i] + 1, i, 0, 100000});
}
sort(Tab.begin(), Tab.end());
int buff = 0;
for (int i = 0; i < n; i++)
{
while (buff < Tab.size() && Tab[buff][0] == i)
{
ST.update(Tab[buff][1], Tab[buff][2], Tab[buff][3]);
buff++;
}
finalHeight[i] = ST.PQ();
}
}
