#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
const int INF = 1e9;
struct Node {
int min_val, max_val;
int lazy_min, lazy_max;
Node() {
min_val = 0; max_val = INF;
lazy_min = 0; lazy_max = INF;
}
};
Node tree[4*MAXN];
void push_lazy(int node, int l, int r) {
if (l == r) return;
int newnode=node<<1;
// propagate max operations
if (tree[node].lazy_max != INF) {
int val = tree[node].lazy_max;
for (int child = newnode+1; child <= newnode+2; child++) {
tree[child].max_val = min(tree[child].max_val, val);
tree[child].min_val = min(tree[child].min_val, val);
tree[child].lazy_max = min(tree[child].lazy_max, val);
tree[child].lazy_min = min(tree[child].lazy_min, val);
}
tree[node].lazy_max = INF;
}
// propagate min operations
if (tree[node].lazy_min != 0) {
int val = tree[node].lazy_min;
for (int child = newnode+1; child <= newnode+2; child++) {
tree[child].max_val = max(tree[child].max_val, val);
tree[child].min_val = max(tree[child].min_val, val);
tree[child].lazy_max = max(tree[child].lazy_max, val);
tree[child].lazy_min = max(tree[child].lazy_min, val);
}
tree[node].lazy_min = 0;
}
}
// to limit the maximum height(op 2)
void update_max(int node, int l, int r, int a, int b, int val) {
push_lazy(node, l, r);
int newnode=node<<1;
if (b < l || a > r) return;
if (a <= l && r <= b) {
tree[node].max_val = min(tree[node].max_val, val);
tree[node].min_val = min(tree[node].min_val, val);
tree[node].lazy_max = min(tree[node].lazy_max, val);
tree[node].lazy_min = min(tree[node].lazy_min, val);
return;
}
int m = (l + r) / 2;
update_max(newnode+1, l, m, a, b, val);
update_max(newnode+2, m+1, r, a, b, val);
tree[node].min_val = min(tree[newnode+1].min_val, tree[newnode+2].min_val);
tree[node].max_val = max(tree[newnode+1].max_val, tree[newnode+2].max_val);
}
//to set a minimum height(op 1)
void update_min(int node, int l, int r, int a, int b, int val) {
push_lazy(node, l, r);
int newnode=node<<1;
if (b < l || a > r) return;
if (a <= l && r <= b) {
tree[node].max_val = max(tree[node].max_val, val);
tree[node].min_val = max(tree[node].min_val, val);
tree[node].lazy_max = max(tree[node].lazy_max, val);
tree[node].lazy_min = max(tree[node].lazy_min, val);
return;
}
int m = (l + r) / 2;
update_min(newnode+1, l, m, a, b, val);
update_min(newnode+2, m+1, r, a, b, val);
tree[node].min_val = min(tree[newnode+1].min_val, tree[newnode+2].min_val);
tree[node].max_val = max(tree[newnode+1].max_val, tree[newnode+2].max_val);
}
void build_final(int node, int l, int r, int finalHeight[]) {
push_lazy(node, l, r);
int newnode=node<<1;
if (l == r) {
finalHeight[l] = tree[node].min_val;
return;
}
int mid = (l + r) / 2;
build_final(newnode+1, l, mid, finalHeight);
build_final(newnode+2, mid+1, r, finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int i = 0; i < 4*MAXN; i++) {
tree[i] = Node();
}
for (int i = 0; i < k; i++) {
if (op[i] == 1) { // add blocks (min height)
update_min(0, 0, n-1, left[i], right[i], height[i]);
} else { // remove blocks (max height)
update_max(0, 0, n-1, left[i], right[i], height[i]);
}
}
// build final heights
build_final(0, 0, n-1, finalHeight);
}
