#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=2e6+10;
struct segment_tree
{
pii it[N * 4];
int Size;
pii combine(pii obj, pii range)
{
obj.fi = max(obj.fi, range.fi);
obj.se = max(obj.se, range.fi);
obj.fi = min(obj.fi, range.se);
obj.se = min(obj.se, range.se);
return obj;
}
void build(int id, int l, int r)
{
if (l == r)
{
it[id] = mp(0,1e5);
return;
}
int mid = (l+r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
it[id] = combine(it[id * 2], it[id * 2 + 1]);
}
void update(int id, int l, int r, int pos, pii range)
{
if (l == r)
{
it[id] = range;
return;
}
int mid = (l+r) / 2;
if (pos <= mid) update(id * 2, l, mid, pos, range);
else update(id * 2 + 1, mid + 1, r, pos, range);
it[id] = combine(it[id * 2], it[id * 2 + 1]);
}
void change(int pos, pii range) { update(1, 1, Size, pos, range);}
int get() { return it[1].fi;}
} seg;
struct event
{
int id;
pii range;
};
vector<event> vt[N];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; ++i)
{
pii range = mp(0,1e5);
if (op[i] == 1) range.fi = height[i];
else range.se = height[i];
vt[left[i]].pb({i + 1, range});
vt[right[i] + 1].pb({i + 1, mp(0,1e5)});
}
seg.Size = k;
seg.build(1, 1, k);
for (int i = 0; i < n; ++i)
{
for (event e : vt[i]) seg.change(e.id, e.range);
finalHeight[i] = seg.get();
}
return;
}
/*int main()
{
//freopen("ss.inp","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}*/
