#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
pair<int,int> lazy[4194304];
bool lazyorder[4194304];
void composeadd(int action, int cur) {
if (lazyorder[cur]) {
if (action > lazy[cur].second) {
lazyorder[cur] = false;
lazy[cur].first = action;
} else {
lazy[cur].first = max(lazy[cur].first, action);
}
} else {
lazy[cur].first = max(lazy[cur].first, action);
}
}
void composeremove(int action, int cur) {
if (lazyorder[cur]) {
lazy[cur].second = min(lazy[cur].second, action);
} else {
if (action < lazy[cur].first) {
lazyorder[cur] = true;
lazy[cur].second = action;
} else {
lazy[cur].second = min(lazy[cur].second, action);
}
}
}
void compose(pair<int,int> action, bool actionorder, int cur) {
if (actionorder) {
composeadd(action.first, cur); composeremove(action.second, cur);
} else {
composeremove(action.second, cur); composeadd(action.first, cur);
}
}
void update(int cur, int mini, int maxi, int a, int b, bool order, pair<int,int> action) {
int dummy;
if (mini == a && maxi == b) {
compose(action, order, cur);
} else if (mini <= a && maxi >= b) {
compose(lazy[cur], lazyorder[cur], cur * 2);
compose(lazy[cur], lazyorder[cur], cur * 2 + 1);
lazy[cur].first = 0; lazy[cur].second = 100000;
dummy = (mini + maxi) / 2;
if (a <= (mini + maxi) / 2) {
update(cur * 2, mini, dummy, a, min(b, dummy), order, action);
}
dummy++;
if (b >= dummy) {
update(cur * 2 + 1, dummy, maxi, max(a, dummy), b, order, action);
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=0;i<4194304;i++) {
lazy[i].first = 0; lazy[i].second = 100000;
lazyorder[i] = true;
}
for (int i=0;i<k;i++) {
if (op[i] == 1) {
update(1, 0, 2097151, left[i], right[i], true, make_pair(height[i], 100000));
} else {
update(1, 0, 2097151, left[i], right[i], false, make_pair(0, height[i]));
}
}
int bruh, sus, maxans, minans, pos;
for (int i=0;i<n;i++) {
bruh = 1048576;
sus = i;
maxans = 100000; minans = 0;
pos = 1;
while (pos < 4194304) {
//cout << minans << ' ' << pos << ' ' << lazy[pos].first << ' ' << lazy[pos].second;
//cout << ' ' << lazyorder[pos] << '\n';
if (!lazyorder[pos]) {
minans = max(minans, lazy[pos].first); minans = min(minans, maxans);
maxans = min(maxans, lazy[pos].second); maxans = max(minans, maxans);
} else {
maxans = min(maxans, lazy[pos].second); maxans = max(minans, maxans);
minans = max(minans, lazy[pos].first); minans = min(minans, maxans);
}
if (bruh > sus) {
pos *= 2;
} else {
sus -= bruh;
pos *= 2; pos++;
}
bruh /= 2;
}
finalHeight[i] = minans; //cout << minans << '\n' << '\n' << '\n';
}
}
