#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
if(n<=10000 and k<=5000){
for(int i=0;i<k;i++){
int l=left[i],r=right[i],he=height[i];
for(int h=l;h<=r;h++){
if(op[i]==1 and finalHeight[h]<he) finalHeight[h]=he;
if(op[i]==2 and finalHeight[h]>he) finalHeight[h]=he;
}
}
}
else{
priority_queue<pair<int,pair<bool,int>>>pq;
multiset<int>s;
int fo;
for(int i=0;i<k;i++){
if(op[i]==1) {
pq.push({-left[i],{0,height[i]}});
pq.push({-right[i]-1,{1,height[i]}});
}
else{
fo=i;
break;
}
}
int cur=0;
while(!pq.empty()){
int val=-*s.begin();
if(-pq.top().first>cur){
while(cur<-pq.top().first){
finalHeight[cur]=max(finalHeight[cur],val);
cur++;
}
}
if(pq.top().second.first){
auto it=s.lower_bound(-pq.top().second.second);
s.erase(it);
}
else{
s.insert(-pq.top().second.second);
}
pq.pop();
}
for(int i=fo;i<k;i++){
pq.push({-left[i],{0,height[i]}});
pq.push({-right[i]-1,{1,height[i]}});
}
s.clear();
// s.insert(0);
cur=0;
while(!pq.empty()){
if(-pq.top().first>cur){
while(cur<-pq.top().first){
if(!s.empty())finalHeight[cur]=min(finalHeight[cur],*s.begin());
cur++;
}
}
if(pq.top().second.first){
auto it=s.lower_bound(pq.top().second.second);
s.erase(it);
}
else{
s.insert(pq.top().second.second);
}
pq.pop();
}
}
}
