#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define all(x) x.begin(),x.end()
#define maxn 2000005
multiset<int> addh,remh;
multiset<ii> ops;
vector<ii> add[2][maxn],rem[2][maxn];
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
for(int i=0;i<k;++i){
add[op[i]-1][left[i]].push_back({i,height[i]});
rem[op[i]-1][right[i]+1].push_back({i,height[i]});
}
int pv=0;
for(int i=0;i<n;++i){
bool have=false;
for(auto[x,h]:add[0][i]){//adding
addh.insert(h);
ops.insert({x,h});
have=true;
}
for(auto[x,h]:rem[0][i]){//adding
addh.erase(addh.find(h));
ops.erase(ops.find({x,h}));
have=true;
}
for(auto[x,h]:add[1][i]){//adding
remh.insert(h);
ops.insert({x,h});
have=true;
}
for(auto[x,h]:rem[1][i]){//adding
remh.erase(remh.find(h));
ops.erase(ops.find({x,h}));
have=true;
}
if(have){
if(addh.empty())pv=0;
else if(remh.empty())pv=*(--addh.end());
else if(*(--addh.end())<=*(remh.begin()))pv=*(--addh.end());
else pv=(*(--ops.end())).second;
}
finalHeight[i]=pv;
}
return;
}
