#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct node {
int left;
int right;
int left_child;
int right_child;
int height;
};
vector <node> memory;
void add(int n, int op, int left, int right, int height) {
if (memory[n].left_child >= 0) {
if (memory[memory[n].left_child].right < left) {
add(memory[n].right_child, op, left, right, height);
}
else {
if (memory[memory[n].left_child].right >= right) {
add(memory[n].left_child, op, left, right, height);
}
else {
add(memory[n].left_child, op, left, memory[memory[n].left_child].right, height);
add(memory[n].right_child, op, memory[memory[n].right_child].left, right, height);
}
}
}
else {
if (memory[n].left == left && memory[n].right == right) {
if (op == 1) {
if (memory[n].height < height) {
memory[n].height = height;
}
}
else {
if (memory[n].height > height) {
memory[n].height = height;
}
}
}
else {
if (memory[n].left == left) {
memory[n].left_child = memory.size();
memory.push_back({left, right, -1, -1, memory[n].height});
add(memory[n].left_child, op, left, right, height);
memory[n].right_child = memory.size();
memory.push_back({right+1, memory[n].right, -1, -1, memory[n].height});
}
else {
memory[n].left_child = memory.size();
memory.push_back({memory[n].left, left-1, -1, -1, memory[n].height});
memory[n].right_child = memory.size();
memory.push_back({left, memory[n].right, -1, -1, memory[n].height});
add(memory[n].right_child, op, left, right, height);
}
}
}
}
void fill_array(int n, int finalHeight[]) {
if (memory[n].left_child >= 0) {
fill_array(memory[n].left_child, finalHeight);
fill_array(memory[n].right_child, finalHeight);
}
else {
for(int i = memory[n].left; i <= memory[n].right; i++) {
finalHeight[i] = memory[n].height;
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memory.push_back({0, n-1, -1, -1, 0});
for(int i = 0; i < k; i++) {
add(0, op[i], left[i], right[i], height[i]);
}
fill_array(0, finalHeight);
return;
}
