#include "overtaking.h"
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
bool debug=0;
#define ll long long
#define pb push_back
#define MP make_pair
#define derr if(debug)cerr
#define plist(x) if(debug){cerr<<"plist "<<#x<<":\n";for(auto e:x){cerr<<e<<" ";}cerr<<"\n";}
vector<set<ll>> arrs; // arr[m] = {timeA, timeB, ...} // (arrs = arrivals)
vector<map<ll, ll>> mp; // mp[m]{time} = speed
int x,m;
vector<ll> S;
set<ll>::iterator it;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> s){
m=M;
x=X;
for(auto e:s){
S.pb(e);
}
arrs = vector<set<ll>>(M);
mp = vector<map<ll, ll>>(M);
// note that S is already sorted
vector<pair<ll, ll>> ns;
for(int i=0; i<N; i++){
ns.pb(MP(W[i], T[i]));
}
sort(ns.begin(), ns.end());
reverse(ns.begin(), ns.end());
// ns is now sorted in order of slowest-to-fastest busses.
vector<ll> dtime,speeds;
for(int i=0; i<N; i++){
speeds.pb(ns[i].first);
dtime.pb(ns[i].second);
}
pair<ll, ll> cpair;
ll cur_time, cur_speed;
ll previous_time, previous_speed;
for(int b=0; b<N; b++){
derr<<"$ b="<<b<<": ";
cur_time = dtime[b];
cur_speed = speeds[b];
derr<<"$ bus with speed "<<cur_speed<<" and dtime "<<cur_time<<"\n";
arrs[0].insert(cur_time);
mp[0][cur_time] = max(mp[0][cur_time], cur_speed);
for(int i=1; i<M; i++){
derr<<"$ i="<<i<<"\n";
// what time would we get there... (lower_bound-1)
it = arrs[i-1].lower_bound(cur_time);
if(it != arrs[i-1].begin()){ // if there is something below...
it--;
previous_time = *it;
previous_speed = mp[i-1][previous_time];
derr<<"$ if was met: ptime="<<previous_time<<", pspeed="<<previous_speed<<"\n";
} else{
previous_time = 0;
previous_speed = 0;
}
derr<<"$ ifelse done.\n";
if(cur_time + cur_speed*(s[i]-s[i-1]) < previous_time+previous_speed*(s[i]-s[i-1])){
cur_time = previous_time+previous_speed*(s[i]-s[i-1]);
} else{
cur_time += cur_speed*(s[i]-s[i-1]);
}
arrs[i].insert(cur_time);
mp[i][cur_time] = max(mp[i][cur_time], cur_speed);
}
}
if(debug)
{
for(int i=0; i<M; i++){
cerr<<"\tfor the sorting station at d="<<s[i]<<":\n";
for(set<ll>::iterator it = arrs[i].begin(); it != arrs[i].end(); it++){
cerr<<"some busses will stop here at t="<<*it<<"\n";
cerr<<"the slowest of these busses takes "<<mp[i][*it]<<" seconds to travel 1km.\n";
cerr<<"\n";
}
cerr<<"\n";
}
}
return;
}
long long arrival_time(long long Y){
ll cur_time = Y;
ll cur_speed = x;
ll previous_speed;
ll previous_time;
for(int i=1; i<m; i++){
it = arrs[i-1].lower_bound(cur_time);
if(it != arrs[i-1].begin()){ // if there is something below...
it--;
previous_time = *it;
previous_speed = mp[i-1][previous_time];
derr<<"$ if was met: ptime="<<previous_time<<", pspeed="<<previous_speed<<"\n";
} else{
previous_time = 0;
previous_speed = 0;
}
if(cur_time + cur_speed*(S[i]-S[i-1]) < previous_time+previous_speed*(S[i]-S[i-1])){
cur_time = previous_time+previous_speed*(S[i]-S[i-1]);
} else{
cur_time += cur_speed*(S[i]-S[i-1]);
}
}
return cur_time;
}
