#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
const int maxn = 2e6+100;
int inf = 1e9;
int n, t[4*maxn][3], l[maxn], r[maxn], ty[maxn], x[maxn];
vector <int> start[maxn], fin[maxn];
void upd(int v, int tl, int tr, int pos, int val, int x)
{
if(pos < tl || tr < pos) return;
if(tl == tr)
{
t[v][x] = val;
return;
}
upd(v * 2, tl, (tl + tr) / 2, pos, val, x);
upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val, x);
t[v][1] = max(t[v * 2][1], t[v * 2 + 1][1]);
t[v][2] = min(t[v * 2][2], t[v * 2 + 1][2]);
}
int get(int v, int tl, int tr, int lboun = 0, int rboun = inf)
{
// cout << "GET " << tl << " " << tr << " " << t[v][1] << " " << t[v][2] << endl;
if(tl == tr)
{
if(max(lboun, t[v][1]) <= min(rboun, t[v][2]))
{
return max(lboun, t[v][1]);
}
// cout << "!!! " << tl << endl;
if(ty[tl] == 1)
return min(rboun, t[v][2]);
else
return max(lboun, t[v][1]);
}
if(max(lboun, t[v * 2 + 1][1]) >= min(rboun, t[v * 2 + 1][2]))
return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, lboun, rboun);
else
return get(v * 2, tl, (tl + tr) / 2, max(lboun,t[v*2+1][1]), min(rboun, t[v*2+1][2]));
}
void build(int v, int tl, int tr)
{
t[v][1] = 0;
t[v][2] = inf;
if(tl == tr)
{
return;
}
build(v * 2, tl, (tl + tr) / 2);
build(v * 2 + 1, (tl + tr) / 2 + 1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
forn(1, i, k)
{
ty[i] = op[i-1];
l[i] = left[i-1]+1;
r[i] = right[i-1]+1;
x[i] = height[i-1];
}
build(1, 1, k);
forn(1, i, k)
{
start[l[i]].pb(i);
fin[r[i]].pb(i);
}
forn(1, iter, n)
{
for(auto i : start[iter])
{
// cout << "UPDATE " << i << " " << x[i] << " " << ty[i] << endl;
upd(1, 1, k, i, x[i], ty[i]);
}
// cout << "LAUNCH GET FOR " << iter << endl;
int go = get(1, 1, k);
finalHeight[iter-1] = go;
for(auto i : fin[iter])
{
// cout << "DELETE " << i << endl;
upd(1, 1, k, i, (ty[i] == 1 ? 0 : inf), ty[i]);
}
}
}
/*int main()
{
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), n);
for (i = 0; i < k; i++){
status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
assert(status == 4);
}
buildWall(n, k, op, left, right, height, finalHeight);
for (j = 0; j < n; j++)
printf("%d\n", finalHeight[j]);
return 0;
}*/
