#include <bits/stdc++.h>
#include "wall.h"
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(s) (int)s.size()
using namespace std;
struct Req {
int val, ind;
bool operator < (const Req &autre) const {
if (val != autre.val)
return val < autre.val;
return ind < autre.ind;
}
};
struct IReq {
int val, ind;
bool operator < (const Req &autre) const {
if (val != autre.val)
return val > autre.val;
return ind < autre.ind;
}
};
struct Event {
bool estDeb;
int date, ind;
bool operator < (const Event &autre) const {
if (date != autre.date)
return date < autre.date;
if (estDeb != autre.estDeb)
return estDeb;
return ind < autre.ind;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int nVals = n, nReqs = k;
vector<Event> events;
for (int iReq = 0; iReq < nReqs; ++iReq){
events.pb({true, left[iReq], iReq});
events.pb({false, right[iReq], iReq});
}
sort(all(events));
set<Req> upperBound;
set<Req> lowerBound;
int pointeur = 0;
for (int iVal = 0; iVal < nVals; ++iVal){
while (pointeur < sz(events) && events[pointeur].date == iVal && events[pointeur].estDeb){
int iReq = events[pointeur].ind;
if (op[iReq] == 1)
lowerBound.insert({height[iReq], iReq});
else
upperBound.insert({height[iReq], iReq});
++pointeur;
}
if (sz(upperBound) == 0 && sz(lowerBound) == 0)
finalHeight[iVal] = 0;
else if (sz(upperBound) >= 1 && sz(lowerBound) >= 1){
if (upperBound.begin()->ind < lowerBound.begin()->ind)
finalHeight[iVal] = lowerBound.begin()->val;
else
finalHeight[iVal] = upperBound.begin()->val;
}
else if (sz(upperBound) >= 1)
finalHeight[iVal] = 0;
else
finalHeight[iVal] = lowerBound.begin()->val;
while (pointeur < sz(events) && events[pointeur].date == iVal && !events[pointeur].estDeb){
int iReq = events[pointeur].ind;
if (op[iReq] == 1)
lowerBound.erase({height[iReq], iReq});
else
upperBound.erase({height[iReq], iReq});
++pointeur;
}
}
return;
}
