#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
int m[8000000], M[8000000];
void push(int v, int tl, int tr)
{
if (tl == tr) return;
m[v*2] = min(m[v*2], m[v]);
m[v*2] = max(m[v*2], M[v]);
M[v*2] = min(M[v*2], m[v]);
M[v*2] = max(M[v*2], M[v]);
m[v*2+1] = min(m[v*2+1], m[v]);
m[v*2+1] = max(m[v*2+1], M[v]);
M[v*2+1] = min(M[v*2+1], m[v]);
M[v*2+1] = max(M[v*2+1], M[v]);
}
void update(int v, int tl, int tr, int l, int r, int val, int op)
{
push(v, tl, tr);
if (r < tl || tr < l) return;
if (l <= tl && tr <= r)
{
if (op)
{
m[v] = min(m[v], val);
M[v] = min(M[v], val);
}
else
{
m[v] = max(m[v], val);
M[v] = max(M[v], val);
}
return;
}
m[v] = INT_MAX, M[v] = INT_MIN;
int tm = (tl + tr) / 2;
update(v*2, tl, tm, l, r, val, op);
update(v*2+1, tm+1, tr, l, r, val, op);
}
void fill(int v, int tl, int tr, int res[])
{
if (tl == tr)
{
res[tl] = m[v];
return;
}
push(v, tl, tr);
int tm = (tl + tr) / 2;
fill(v*2, tl, tm, res);
fill(v*2+1, tm+1, tr, res);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for (int i = 0; i < k; i++)
update(1, 0, n-1, left[i], right[i], height[i], op[i] - 1);
fill(1, 0, n-1, finalHeight);
}
