#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define ll long long
#define mp make_pair
#define ff first
#define ss second
const int inf = 2e9;
vector<pair<int,int>> a;
vector<int> pos;
vector<queue<int>> vq;
void build(int p,int l,int r)
{
if(l == r)pos[l] = p;
else
{
int m = (l + r) / 2;
build(p*2,l,m);
build(p*2+1,m+1,r);
}
if(l > r)
{
cout<<-1;
return;
}
a[p].ff = 0;
a[p].ss = inf;
return ;
}
void change(int p)
{
if(p <= 0)return ;
int mx = min(a[p*2].ss,a[p*2+1].ss);
int mn = max(a[p*2].ff,a[p*2+1].ff);
if(mn > mx)
{
if(mn == a[p*2+1].ff)mx = mn;
else mn = mx;
}
a[p].ff = mn;
a[p].ss = mx;
change(p/2);
return ;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
a.resize(k * 4);
pos.resize(k);
vq.resize(n+1);
build(1,0,k-1);
for(int i = 0;i < k;i++)vq[left[i]].push(i);
for(int i = 0;i < k;i++)vq[right[i]+1].push(i);
for(int i = 0;i < n;i++)
{
while(!vq[i].empty())
{
int v = vq[i].front();
vq[i].pop();
if(a[pos[v]] == mp(0,inf))
{
if(op[v] == 1)a[pos[v]].ff = height[v];
else a[pos[v]].ss = height[v];
}
else a[pos[v]] = mp(0,inf);
change(pos[v]/2);
}
finalHeight[i] = a[1].ff;
}
return ;
}
