#include "wall.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 2E6;
const int MAXH = 1E6 + 10;
int currentlyIn[MAXH];
int currentlyInMin[MAXH];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
vector<queue<int>> prefixAdd(n+1);
vector<queue<int>> prefixRem(n+1);
vector<queue<int>> prefixAddMin(n+1);
vector<queue<int>> prefixRemMin(n+1);
currentlyInMin[MAXH-1] = 1E9;
currentlyIn[0] = 1E9;
priority_queue<int> pq;
pq.push(0);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
prefixAdd[left[i]].push(height[i]);
prefixRem[right[i]+1].push(height[i]);
continue;
}
prefixAddMin[left[i]].push(height[i]);
prefixRemMin[right[i]+1].push(height[i]);
}
for (int i = 0; i < n; i++) {
for (; !prefixRem[i].empty(); prefixRem[i].pop()) {
int val = prefixRem[i].front();
currentlyIn[val]--;
}
for (; !prefixAdd[i].empty(); prefixAdd[i].pop()) {
int val = prefixAdd[i].front();
if (!currentlyIn[val]) pq.push(val);
currentlyIn[val]++;
}
for (; !currentlyIn[pq.top()]; pq.pop());
finalHeight[i] = pq.top();
}
for (; !pq.empty(); pq.pop());
pq.push(-(MAXH-1));
for (int i = 0; i < n; i++) {
for (; !prefixRemMin[i].empty(); prefixRemMin[i].pop()) {
int val = prefixRemMin[i].front();
currentlyInMin[val]--;
}
for (; !prefixAddMin[i].empty(); prefixAddMin[i].pop()) {
int val = prefixAddMin[i].front();
if (!currentlyInMin[val]) pq.push(-val);
currentlyInMin[val]++;
}
for (; !currentlyInMin[abs(pq.top())]; pq.pop());
finalHeight[i] = min(finalHeight[i], abs(pq.top()));
}
return;
}
