#include "wall.h"
#include <algorithm>
#include <set>
#include <vector>
#include <cstdio>
#define PB push_back
#define debug(...) //fprintf(stderr, __VA_ARGS__)
using namespace std;
const int LOG = 21;
const int N = 1 << LOG;
const int OO = 0x7FFFFFFF;
struct node {
int a, b;
node() : a(0), b(OO) {}
node(int a, int b) : a(a), b(b) {}
};
node t[2 * N];
void merge(int &a, int &b, int l, int r) {
a = min(r, max(l, a));
b = max(l, min(r, b));
}
void propagate(int u) {
merge(t[2 * u].a, t[2 * u].b, t[u].a, t[u].b);
merge(t[2 * u + 1].a, t[2 * u + 1].b, t[u].a, t[u].b);
t[u].a = 0;
t[u].b = OO;
}
void update(int l, int r, int a, int b, int u = 1, int lo = 0, int hi = N) {
if(r <= lo || hi <= l) {
return;
}
if(l <= lo && hi <= r) {
merge(t[u].a, t[u].b, a, b);
return;
}
int mi = (lo + hi) / 2;
propagate(u);
update(l, r, a, b, 2 * u, lo, mi);
update(l, r, a, b, 2 * u + 1, mi, hi);
}
void query(int u = 1, int lo = 0, int hi = N) {
if(u >= N) { return; }
int mi = (lo + hi) / 2;
propagate(u);
query(2 * u, lo, mi);
query(2 * u + 1, mi, hi);
}
void buildWall(int n, int k, int op[], int lft[], int rgt[], int hgt[], int fnl[]){
for(int i = 0; i < k; ++i) {
int a, b;
if(op[i] == 1) {
a = hgt[i];
b = OO;
} else {
a = 0;
b = hgt[i];
}
update(lft[i], rgt[i] + 1, a, b);
}
query();
for(int i = 0; i < n; ++i) {
fnl[i] = t[N + i].a;
debug("%d %d\n", i, fnl[i]);
}
return;
}
