#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#include "wall.h"
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=2e6+5,K=5e5+5;
pii t[K*4];
vector<int> L[N],R[N];
pii merge(pii a, pii b) {
pii c;
if (b.f==-1) return b;
if (a.f==-1) {
c.f=-1;
if (a.s<b.f) c.s=b.f;
else if (a.s>b.s) c.s=b.s;
else c.s=a.s;
return c;
}
int l=max(a.f,b.f),r=min(a.s,b.s);
if (l<=r) return {l,r};
if (a.s<b.s) return {-1,b.f};
else return {-1,b.s};
}
void update(int v, int tl, int tr, int ind, int x, int y) {
if (tl==tr) {
t[v]={x,y};
return;
}
int mid=(tl+tr)/2;
if (ind<=mid) update(v*2,tl,mid,ind,x,y);
else update(v*2+1,mid+1,tr,ind,x,y);
t[v]=merge(t[v*2],t[v*2+1]);
}
pii query(int v, int tl, int tr, int l, int r) {
if (tl==l && tr==r) return t[v];
int mid=(tl+tr)/2;
if (r<=mid) return query(v*2,tl,mid,l,r);
else if (mid+1<=l) return query(v*2+1,mid+1,tr,l,r);
else return merge(query(v*2,tl,mid,l,mid),query(v*2+1,mid+1,tr,mid+1,r));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=0; i<k; i++) {
L[left[i]].pb(i);
R[right[i]].pb(i);
}
for (int i=0; i<k; i++) update(1,0,k-1,i,0,1e9);
for (int i=0; i<n; i++) {
// cout<<"I "<<i<<endl;
//
// for (int i=0; i<k*4; i++) {
// cout<<"TTT "<<i<<" "<<t[i].f<<" "<<t[i].s<<endl;
// }
if (i) {
for (auto x:R[i-1]) {
update(1,0,k-1,x,0,1e9);
}
}
for (auto x:L[i]) {
if (op[x]==1) update(1,0,k-1,x,height[x],1e9);
else update(1,0,k-1,x,0,height[x]);
}
pii ans=query(1,0,k-1,0,k-1);
if (ans.f==-1) finalHeight[i]=ans.s;
else finalHeight[i]=ans.f;
}
}
