#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
vector<pair <pair <int,int>, pair<int,int> > > t;
void add(int i, int h, int ph){
if (i == 24) {
cin.tie(0);
}
if (t[i].se.se == -1) {
t[i].se = {h, ph};
return;
}
if (t[i].se.se != ph) {
swap(t[i].fi, t[i].se);
if (ph == 1) {
t[i].se.fi = min(t[i].se.fi, t[i].fi.fi);
}
else t[i].se.fi = max(t[i].se.fi, t[i].fi.fi);
}
if (ph == 1) t[i].se.fi = max(t[i].se.fi, h);
else t[i].se.fi = t[i].se.se == -1 ? h : min(t[i].se.fi, h);
t[i].se.se = ph;
}
void merge(int i){
if (t[i].fi.se != -1) {
add(i * 2, t[i].fi.fi, t[i].fi.se);
add(i * 2 + 1, t[i].fi.fi, t[i].fi.se);
}
if (t[i].se.se != -1) {
add(i * 2, t[i].se.fi, t[i].se.se);
add(i * 2 + 1, t[i].se.fi, t[i].se.se);
}
t[i] = { {0, -1}, {0, -1}};
}
void update(int i, int l, int r, int Ql, int Qr, int h, int ph) {
if (l != r) merge(i);
if (l > Qr || r < Ql) return;
if (l >= Ql && r <= Qr) {
add(i, h, ph);
return;
}
int mid = (l + r) / 2;
update(i * 2, l, mid, Ql, Qr, h, ph);
update(i * 2 + 1, mid + 1, r, Ql, Qr, h, ph);
}
vector<int> ans;
void Query(int i, int l, int r) {
if (l == r) {
auto x = t[i];
if (x.se.se == 1) ans[l] = x.se.fi;
else ans[l] = min(x.fi.fi, x.se.fi);
return;
}
int mid = (l + r) / 2;
merge(i);
Query(i * 2, l, mid);
Query(i * 2 + 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
t.resize(4 * n , { {0, -1}, {0, -1}}); ans.resize(n);
for (int i = 0; i < k; i++) update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
Query(1, 0, n-1);
for (int i = 0; i < n; i++) {
finalHeight[i] = ans[i];
}
}
