#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(xx) xx.begin(),xx.end()
pii propmini(pii state,int minimise) {
if (minimise == -1) return state;
if (state.ss != -1) {
if (state.ss <= minimise) return state;
}
if (state.ff < minimise) return {state.ff,minimise};
return {minimise,minimise};
}
pii propmaxi(pii state,int maximise) {
if (maximise == -1) return state;
if (state.ff == -1) {
if (state.ss != -1 && state.ss <= maximise) return {maximise,maximise};
return {maximise,state.ss};
}
if (state.ss == -1) {
if (state.ff >= maximise) return state;
return {maximise,state.ss};
}
if (maximise < state.ff) return state;
if (maximise > state.ss) return {maximise,maximise};
return {maximise,state.ss};
}
struct ST {
vector<pii> lazy;
vector<pii> t;
ST(int nn) {
lazy.assign(4*nn+1,pii{-1,-1});
t.assign(4*nn+1,pii{-1,-1});
}
void push(int node,bool leaf) {
t[node] = propmaxi(t[node],lazy[node].ff);
t[node] = propmini(t[node],lazy[node].ss);
if (!leaf) {
lazy[2*node] = propmaxi(lazy[2*node],lazy[node].ff);
lazy[2*node] = propmini(lazy[2*node],lazy[node].ss);
lazy[2*node+1] = propmaxi(lazy[2*node+1],lazy[node].ff);
lazy[2*node+1] = propmini(lazy[2*node+1],lazy[node].ss);
}
lazy[node] = {-1,-1};
}
void mini(int node,int l,int r,int L,int R,int v) {
push(node,l==r);
if (l > R || r < L) return;
if (l >= L && r <= R) {
lazy[node] = propmini(lazy[node],v);
push(node,l==r);
return;
}
int m = (l+r) >> 1;
mini(2*node,l,m,L,R,v);
mini(2*node+1,m+1,r,L,R,v);
}
void maxi(int node,int l,int r,int L,int R,int v) {
push(node,l==r);
if (l > R || r < L) return;
if (l >= L && r <= R) {
lazy[node] = propmaxi(lazy[node],v);
push(node,l==r);
return;
}
int m = (l+r) >> 1;
maxi(2*node,l,m,L,R,v);
maxi(2*node+1,m+1,r,L,R,v);
}
pii query(int node,int l,int r,int p) {
push(node,l==r);
if (l == r) return t[node];
int m = (l+r) >> 1;
if (p<=m) return query(2*node,l,m,p);
return query(2*node+1,m+1,r,p);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
ST st(n);
pii p = {-1,-1};
for (int i=0;i<k;i++){
if (op[i] == 1) {
//ADD
st.maxi(1,1,n,left[i]+1,right[i]+1,height[i]);
}
else {
//REM
st.mini(1,1,n,left[i]+1,right[i]+1,height[i]);
}
}
for (int i=0;i<n;i++) {
pii p = st.query(1,1,n,i+1);
if (p.ff!=-1) finalHeight[i] = p.ff;
else finalHeight[i] = 0;
}
return;
}
