#include "wall.h"
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int MAXN = 2E6;
const int MAXH = 1E6 + 10;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
vector<pair<int, pair<int,int>>> fp;
multiset<int> big;
multiset<int> small;
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
fp.push_back({left[i],{height[i],1}});
fp.push_back({right[i]+1,{-height[i],1}});
continue;
}
fp.push_back({left[i],{height[i],0}});
fp.push_back({right[i]+1,{-height[i],0}});
}
sort(fp.begin(),fp.end());
int j = 0;
for (int i = 0; i < n; i++) {
while (fp[j].first <= i && j < fp.size()) {
auto [val, type] = fp[j].second;
if (type == 1) {
if (val >= 0) {
big.insert(val);
} else {
big.erase(-val);
}
} else {
if (val >= 0) {
small.insert(val);
} else {
small.erase(-val);
}
}
j++;
}
if (!big.empty())
finalHeight[i] = *prev(big.end());
if (!small.empty())
finalHeight[i] = min(finalHeight[i], *small.begin());
}
return;
}
