#include <bits/stdc++.h>
#include "wall.h"
#define pb push_back
#define mp(x...) array<int,2>({x})
using namespace std;
//#define DEBUGGING
#ifdef DEBUGGING
#define debug(x) cout << (#x) << ": " << x << "\n"
#else
#define debug(x)
#endif
int k;
constexpr static int MXSIZE = 5e5;
constexpr static int MXST = MXSIZE<<2;
constexpr static int MXHEIGHT = 1e5;
constexpr static int MNHEIGHT = 0;
array<int, 2> st[MXST];
array<int, 2> merge(array<int, 2> l, array<int, 2> r)
{
return mp(min(max(l[0], r[0]), r[1]), max(min(l[1], r[1]), r[0]));
}
void create()
{
for (int i = 1; i < (k<<2); i++) st[i] = mp(MNHEIGHT, MXHEIGHT);
}
void update(int l, int r, int index, int i, array<int, 2> val)
{
if (i >= r || l > i)
return;
if (l + 1 == r)
{
st[index] = val;
return;
}
int m = l+r>>1;
update(l, m, index<<1, i, val);
update(m, r, (index<<1)|1, i, val);
st[index] = merge(st[index<<1], st[(index<<1)|1]);
}
array<int, 2> query(int l, int r, int index, int ss, int ee)
{
if (l >= ee || ss >= r)
return mp(MNHEIGHT, MXHEIGHT);
if (ee >= r && l >= ss)
return st[index];
int m = l+r>>1;
array<int, 2> lres = query(l, m, index<<1, ss, ee);
array<int, 2> rres = query(m, r, (index<<1)|1, ss, ee);
return merge(lres, rres);
}
void update(int i, array<int, 2> val) { update(0, k, 1, i, val); }
array<int, 2> query(int ss, int ee) { return query(0, k, 1, ss, ee); }
void buildWall(int n, int kk, int op[], int left[], int right[], int height[], int finalHeight[])
{
k = kk;
create();
vector<array<int, 2>> lq, rq;
for (int i = 0; i < k; i++)
{
lq.pb(mp(left[i], i));
rq.pb(mp(right[i]+1, i));
}
sort(lq.begin(), lq.end());
sort(rq.begin(), rq.end());
int lj = 0, rj = 0;
for (int i = 0; i < n; i++)
{
while (lj < k && lq[lj][0] == i)
{
int index = lq[lj][1];
if (op[index] == 1)
update(index, mp(height[index], MXHEIGHT));
else
update(index, mp(MNHEIGHT, height[index]));
lj++;
}
while (rj < k && rq[rj][0] == i) update(rq[rj++][1], mp(MNHEIGHT, MXHEIGHT));
array<int, 2> res = query(0, k);
finalHeight[i] = res[0];
}
}
