#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2000000;
const int MAX_K = 500000;
const int MAX_VAL = 100000;
struct Range {
int l, r;
Range():l(0), r(MAX_VAL + 1) {}
Range(int _l, int _r):l(_l), r(_r) {}
Range operator+ (const Range &x) const {
return Range(max(l, x.l), min(r, x.r));
}
};
Range aint[1+4*MAX_K];
void update(int poz, Range x, int l = 0, int r = MAX_K - 1, int nod = 1) {
if(poz < l || r < poz) return;
if(l == r)
aint[nod] = x;
else {
int mid = (l + r) / 2;
update(poz, x, l, mid, 2 * nod);
update(poz, x, mid + 1, r, 2 * nod + 1);
aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
}
bool intersect(const Range &x) {
return x.l > x.r;
}
int query(Range &x, int l = 0, int r = MAX_K - 1, int nod = 1) {
if(l == r)
return l;
else {
int mid = (l + r) / 2;
if(intersect(x + aint[2 * nod + 1]))
return query(x, mid + 1, r, 2 * nod + 1);
else {
x = x + aint[2 * nod + 1];
return query(x, l, mid, 2 * nod);
}
}
}
struct Event {
Range x;
int poz;
};
vector<Event> evs[MAX_N + 1];
Range mod[MAX_K];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; ++i) {
if(op[i] == 1)
evs[left[i]].push_back({Range(height[i], MAX_VAL + 1), i});
else
evs[left[i]].push_back({Range(0, height[i]), i});
evs[right[i] + 1].push_back({Range(), i});
}
for(int i = 0; i < n; ++i) {
for(auto it: evs[i]) {
update(it.poz, it.x);
mod[it.poz] = it.x;
}
Range last = Range();
int poz;
poz = query(last);
if((last + mod[poz]).l <= last.r)
finalHeight[i] = (last + mod[poz]).l;
else if((last + mod[poz]).l > last.r)
finalHeight[i] = last.r;
else
finalHeight[i] = last.l;
}
}
