#include "wall.h"
#include <bits/stdc++.h>
const int MX = 100000;
struct Node {
Node *l, *r;
int min, max;
Node() : l(nullptr), r(nullptr), min(0), max(MX) { }
~Node() {
if (l)
delete(l);
if (r)
delete(r);
}
void update() {
if (!l) l = new Node;
if (!r) r = new Node;
min = std::max(l->min, r->min);
max = std::min(l->max, r->max);
if (min > max) {
if (l->min > r->max)
min = max = r->max;
if (l->max < r->min)
min = max = r->min;
}
}
};
Node* head = new Node;
void add(int index, int min, int max, int left, int right, Node*& node) {
if (!node)
node = new Node;
if (left == right) {
node->min = min;
node->max = max;
return;
}
int mid = (left + right) >> 1;
if (mid >= index) add(index, min, max, left, mid, node->l);
else add(index, min, max, mid + 1, right, node->r);
node->update();
}
struct Operation {
int index;
int min, max;
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
std::vector <std::vector <Operation>> operations(n + 1);
for (int i = 0; i < k; i++) {
operations[left[i]].push_back({ i, op[i] ? height[i] : 0, op[i] ? MX : height[i] });
operations[right[i] + 1].push_back({ i, 0, MX });
}
for (int i = 0; i < n; i++) {
for (const auto& o : operations[i])
add(o.index, o.min, o.max, 0, k - 1, head);
finalHeight[i] = head->min;
}
delete(head);
}
//int main() {
//int n = 10;
//int k = 6;
//int op[6] = { 1, 0, 0, 1, 1, 0 };
//int left[6] = { 1, 4, 3, 0, 2, 6 };
//int right[6] = { 8, 9, 6, 5, 2, 7 };
//int height[6] = { 4, 1, 5, 3, 5, 0 };
//int finalHeight[10];
//buildWall(n, k, op, left, right, height, finalHeight);
//for (int i = 0; i < n; i++)
//std::cout << finalHeight[i] << " \n"[i == n - 1];
//}
