#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
struct st
{
int t, v, o;
st(){
t = v = o = -1;
}
st(int a, int b, int c)
{
t = a;
v = b;
o = c;
}
};
vector <st> t[N * 4], vec;
int n;
void update (int time, int type, int l, int r, int val, int v = 1, int tl = 1, int tr = n)
{
if (l > tr || tl > r)
return;
if (l <= tl && tr <= r)
{
t[v].emplace_back( st( time, val, type ) );
return;
}
int tm = (tl + tr) >> 1;
update (time, type, l, r, val, v + v, tl, tm);
update (time, type, l, r, val, v + v + 1, tm + 1, tr);
}
void Do (int pos, int v = 1, int tl = 1, int tr = n)
{
if (pos > tr || pos < tl) return;
for (auto to : t[v])
vec.emplace_back(to);
if(tl == tr) return;
int tm = (tl + tr) >> 1;
Do( pos, v + v, tl, tm );
Do( pos, v + v + 1, tm + 1, tr );
}
bool cmp (st a, st b)
{
return a.t < b.t;
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int ans[])
{
n = N;
for (int i = 0; i < k; i++)
update( i, op[i], left[i] + 1, right[i] + 1, height[i] );
for (int i = 1; i <= n; i++)
{
vec.clear();
Do( i );
sort( vec.begin(), vec.end() , cmp);
// cout<<i << endl;
//
// for (auto to : vec)
// {
// cout << to.t << " " << to.v << " " << to.o << endl;
// }
// system("pause");
st a, b;
int fl = -1;
for (auto to : vec)
{
if (fl != -1)
{
if (to.o == 1 && to.v > fl)
fl = to.v;
else if (to.o == 2 && to.v < fl)
fl = to.v;
continue;
}
if (a.t == -1)
a = to;
else if (b.t == -1)
{
if (to.o == 1)
{
if (a.o == 2)
{
if (a.v <= to.v)
fl = to.v;
else
b = to;
}
else if (to.v > a.v)
a = to;
}
else
{
if (a.o == 1)
{
if (a.v >= to.v)
fl = to.v;
else
b = to;
}
else if (to.v < a.v)
a = to;
}
}
else
{
if (to.o == 1 && to.v > a.v)
a = to;
else if (to.o == 2 && to.v < b.v)
b = to;
}
if (a.o == 2 && b.o == 1)
swap(a, b);
}
if (fl != -1)
ans[i - 1] = fl;
else
{
if (a.o == 2)
ans[i - 1] = 0;
else
ans[i - 1] = (a.v == -1 ? 0 : a.v);
}
}
}
