#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define pb push_back
#define pp pair<int, int>
#define F first
#define S second
#define MP make_pair
const int BIT = 19;
const int N = 2 * 1e6 + 100;
const int K = (1 << BIT);
const int INF = 2 * 1e9;
vector<int> sweep[2][N];
pp t[2 * K];
pp merge(pp a, pp b){
a.F = min(a.F, b.F);
a.F = max(a.F, b.S);
a.S = min(a.S, b.F);
a.S = max(a.S, b.S);
return a;
}
void upd(int x, pp p){
x += K; t[x] = p;
while (x > 1){
x /= 2; t[x] = merge(t[2 * x], t[2 * x + 1]);
}
}
//void buildWall(int n, int k, vector<int> op, vector<int> left, vector<int> right, vector<int> height, vector<int> finalHeight){
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 1; i < 2 * K; ++i)
t[i] = MP(INF, -INF);
for (int i = 0; i < k; ++i){
sweep[0][left[i]].pb(i);
sweep[1][right[i]].pb(i);
}
for (int i = 0; i < n; ++i){
for (int x: sweep[0][i])
upd(x, op[x] == 1 ? MP(INF, height[x]) : MP(height[x], -INF));
finalHeight[i] = merge(MP(0, 0), t[1]).F;
for (int x: sweep[1][i]) upd(x, MP(INF, -INF));
}
/*for (int i = 0; i < n; ++i)
cout << finalHeight[i] << ' ';*/
}
