#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
using namespace std;
struct node {
int mn, mx, st, end;
node* left;
node* right;
node(int MN, int MX, int ST, int END) {
mn = MN, mx = MX;
st = ST, end = END;
left = nullptr;
right = nullptr;
};
};
void propogate(node* now) {
if (now->left == nullptr)
now->left = new node(0, 0, now->st, (now->st+now->end)/2);
if (now->right == nullptr)
now->right = new node(0, 0, (now->st+now->end)/2+1, now->end);
if (now->mx != -1) {
now->left->mx = max(now->left->mx, now->mx);
now->right->mx = max(now->right->mx, now->mx);
if (now->left->mn != -1)
now->left->mn = max(now->left->mn, now->mx);
if (now->right->mn != -1)
now->right->mn = max(now->right->mn, now->mx);
now->mx = -1;
}
if (now->mn != -1) {
if (now->left->mn != -1)
now->left->mn = min(now->left->mn, now->mn);
else
now->left->mn = now->mn;
if (now->right->mn != -1)
now->right->mn = min(now->right->mn, now->mn);
else
now->right->mn = now->mn;
now->left->mx = min(now->left->mx, now->mn);
now->right->mx = min(now->right->mx, now->mn);
now->mn = -1;
}
}
void update(node* now, int& l, int& r, int& v, int& t) {
if (now->st > r || now->end < l)
return;
if (l <= now->st && now->end <= r) {
if (t == 1) {
now->mx = max(now->mx, v);
if (now->mn != -1)
now->mn = max(now->mn, v);
} else {
if (now->mn != -1)
now->mn = min(now->mn, v);
else
now->mn = v;
now->mx = min(now->mx, v);
}
return;
}
propogate(now);
update(now->left, l, r, v, t);
update(now->right, l, r, v, t);
}
vector<int> ans;
void query(node* now) {
if (now->st == now->end) {
ans[now->st] = now->mx;
return;
}
propogate(now);
query(now->left);
query(now->right);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
node* root = new node(0, 0, 0, n-1);
for (int i = 0; i < k; i++) {
update(root, left[i], right[i], height[i], op[i]);
}
ans.resize(n, 0);
query(root);
for (int i = 0; i < n; i++)
finalHeight[i] = ans[i];
return;
}
