#include "wall.h"
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<19)
#define INF 1145141919
#define pb push_back
struct Node {
int a, b;
Node(int a, int b) : a(a), b(b) {}
Node() : a(INF), b(0) {}
int f(int x) { return min(a, max(b, x)); }
};
inline Node op(const Node &l, const Node &r) {
return Node(min(r.a, max(l.a, r.b)), max(l.b, r.b));
}
Node seg[MAX_N*2-1];
void update(int k, const Node &v) {
k += MAX_N-1;
seg[k] = v;
while (k > 0) {
k = (k-1)/2;
seg[k] = op(seg[k*2+1], seg[k*2+2]);
}
}
vector<int> GL[2000000], GR[2000000];
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
rep(i, K) GL[left[i]].pb(i);
rep(i, K) GR[right[i]].pb(i);
rep(i, N) {
for (int x : GL[i]) {
if (op[x] == 1) update(x, Node(INF, height[x]));
else update(x, Node(height[x], 0));
}
finalHeight[i] = seg[0].f(0);
for (int x : GR[i]) update(x, Node());
}
}
