#include "wall.h"
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 1e9;
struct Node {
int low, high;
};
Node tree[8000005]; // 4 * N o'lchamli segmentlar daraxti
// Yangi cheklovlarni joriy cheklovlarga tatbiq etish
void apply(int node, int op, int h) {
if (op == 1) { // Add amal (pastdan cheklov)
tree[node].low = max(tree[node].low, h);
tree[node].high = max(tree[node].high, h);
} else { // Remove amal (tepadan cheklov)
tree[node].low = min(tree[node].low, h);
tree[node].high = min(tree[node].high, h);
}
}
// Ota tugun cheklovlarini bola tugunlarga o'tkazish
void push(int node, int l, int r) {
if (l != r) {
apply(2 * node, 1, tree[node].low);
apply(2 * node, 2, tree[node].high);
apply(2 * node + 1, 1, tree[node].low);
apply(2 * node + 1, 2, tree[node].high);
tree[node].low = 0;
tree[node].high = INF;
}
}
void update(int node, int l, int r, int ql, int qr, int op, int h) {
if (ql <= l && r <= qr) {
apply(node, op, h);
return;
}
push(node, l, r);
int mid = (l + r) / 2;
if (ql <= mid) update(2 * node, l, mid, ql, qr, op, h);
if (qr > mid) update(2 * node + 1, mid + 1, r, ql, qr, op, h);
}
// Yakuniy natijalarni yig'ish
void getFinal(int node, int l, int r, int finalHeight[]) {
if (l == r) {
finalHeight[l] = tree[node].low;
return;
}
push(node, l, r);
int mid = (l + r) / 2;
getFinal(2 * node, l, mid, finalHeight);
getFinal(2 * node + 1, mid + 1, r, finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
// Dastlabki holatni sozlash
for (int i = 0; i < 4 * n + 5; i++) {
tree[i].low = 0;
tree[i].high = INF;
}
for (int i = 0; i < k; i++) {
update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
getFinal(1, 0, n - 1, finalHeight);
}
