#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 998244353;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
struct Tree{
Tree *left, *right;
int lo, hi;
int lazymin = 0;
int lazymax = 0;
Tree(int lo, int hi) : lo(lo), hi(hi){
if(lo+1 == hi) return;
int mid = (lo+hi)/2;
left = new Tree(lo, mid);
right = new Tree(mid, hi);
}
void update(int from, int to, int h, int op){
if(to <= lo || from >= hi) return;
push();
if(from <= lo && to >= hi){
if(op == 1){
lazymin = max(lazymin, h);
lazymax = max(lazymax, h);
}
else{
lazymax = min(lazymax, h);
lazymin = min(lazymin, h);
}
return;
}
left->update(from, to, h, op);
right->update(from, to, h, op);
}
void push(){
if(lo+1 == hi) return;
left->lazymax = min(left->lazymax, lazymax);
left->lazymax = max(left->lazymax, lazymin);
right->lazymax = min(right->lazymax, lazymax);
right->lazymax = max(right->lazymax, lazymin);
left->lazymin = max(left->lazymin, lazymin);
left->lazymin = min(left->lazymin, lazymax);
right->lazymin = max(right->lazymin, lazymin);
right->lazymin = min(right->lazymin, lazymax);
lazymin = 0;
lazymax = inf;
}
int ans(vi* ans, int i){
push();
if(lo+1 == hi) {
assert(lazymin == lazymax);
ans->at(i) = lazymin;
return i+1;
}
i = left->ans(ans, i);
i = right->ans(ans, i);
return i;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
Tree st(0, n);
for(int i = 0; i < k; i++){
st.update(left[i], right[i]+1, height[i], op[i]);
}
vi *ans = new vi(n);
st.ans(ans, 0);
for(int i = 0; i < n; i++) finalHeight[i] = ans->at(i);
}
