#include "wall.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <chrono>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast \
ios_base::sync_with_stdio (false); \
cin.tie (NULL); \
cout.tie (NULL)
using namespace std;
pair <ll,ll> t[4*2000000+40];
pair <ll,ll> combine(pair <ll,ll> p1, pair <ll,ll> p2)
{
if(p1.ss<p2.ff)
return {p2.ff,p2.ff};
else if (p1.ff>p2.ss)
return {p2.ss,p2.ss};
else return make_pair(max(p1.ff,p2.ff), min(p1.ss,p2.ss));
}
void push(int v)
{
pair <ll,ll> p={-INF,INF};
if(t[v]!=p)
{
t[2*v]=combine(t[2*v],t[v]);
t[2*v+1]=combine(t[2*v+1],t[v]);
t[v]={-INF,INF};
}
}
void update(ll v, ll tl, ll tr, ll l, ll r, pair <ll,ll> add) {
if (l > r)
return;
if (l == tl && r == tr) {
t[v] = combine(t[v],add);
} else {
push(v);
ll tm = (tl + tr) / 2;
update(v*2, tl, tm, l, min(r, tm), add);
update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
//t[v]=combine(t[2*v],t[2*v+1]);
}
}
pair<ll,ll> get(ll v, ll tl, ll tr, ll pos) {
if (tl == tr)
return t[v];
ll tm = (tl + tr) / 2;
if (pos <= tm)
return combine(get(v*2, tl, tm, pos), t[v]);
else
return combine(get(v*2+1, tm+1, tr, pos),t[v]);
}
void buildWall(int n, int k, int Op[], int left[], int right[], int height[], int finalHeight[]){
rep(i,0,4*2000000+40)
t[i]={-INF,INF};
rep(itr,0,k-1)
{
int op=Op[itr];
if(op==1)
{
ll l=left[itr], r=right[itr], v=height[itr];
pair <ll,ll> p=make_pair(v,INF);
update(1,0,n-1,l,r,p);
}
else
{
ll l=left[itr], r=right[itr], v=height[itr];
pair <ll,ll> p=make_pair(-INF,v);
update(1,0,n-1,l,r,p);
}
}
rep(i,0,n-1)
{
pair <ll,ll> p;
p=get(1,0,n-1,i);
if(0<p.ff)
finalHeight[i]=p.ff;
else if (0>=p.ff && 0<=p.ss)
finalHeight[i]=0;
else if (0>p.ss)
finalHeight[i]=p.ss;
}
//cout<<endl<<endl<<t[1].ff<<" "<<t[1].ss<<endl<<t[2].ff<<" "<<t[2].ss<<endl<<t[3].ff<<" "<<t[3].ss;
}
