#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
const int INF = 2000000000;
const int maxn = 2000000;
const int segn = (1 << 22);
int seg[segn][2];
void addlower(int p, int l, int r, int k) {
MAX(seg[p][0], k);
MAX(seg[p][1], k);
}
void addupper(int p, int l, int r, int k) {
MIN(seg[p][1], k);
MIN(seg[p][0], seg[p][1]);
}
void push(int p, int l, int r) {
if (seg[p][0] == seg[p][1] && seg[p][1] == INF) return;
if (l == r) return;
int mid = (l + r) >> 1;
addlower((p << 1), l, mid, seg[p][0]);
addlower((p << 1) | 1, mid + 1, r, seg[p][0]);
addupper((p << 1), l, mid, seg[p][1]);
addupper((p << 1) | 1, mid + 1, r, seg[p][1]);
seg[p][0] = 0, seg[p][1] = INF;
}
void upd(int p, int l, int r, int L, int R, int K, char C) {
push(p, l, r);
if (r < L || R < l) return;
if (L <= l && r <= R) {
(C == 'L' ? addlower(p, l, r, K) : addupper(p, l, r, K));
return;
}
int mid = (l + r) >> 1;
upd(p << 1, l, mid, L, R, K, C);
upd((p << 1) | 1, mid + 1, r, L, R, K, C);
}
void finalize(int p, int l, int r, int finalHeight[]) {
push(p, l, r);
if (l == r) {
finalHeight[l] = seg[p][0];
return;
}
int mid = (l + r) >> 1;
finalize(p << 1, l, mid, finalHeight);
finalize((p << 1) | 1, 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 < segn; i++) seg[i][0] = 0, seg[i][1] = INF;
for (int i = 0; i < k; i++)
if (op[i] == 1)
upd(1, 0, n - 1, left[i], right[i], height[i], 'L');
else
upd(1, 0, n - 1, left[i], right[i], height[i], 'U');
finalize(1, 0, n - 1, finalHeight);
}
