#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, goes_to; // 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);
goes_to = 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;
ll lower_goto, val;
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";
for(int i=0; i<M-1; i++){
derr<<"$ i="<<i<<"\n";
// what time would we get to the next... (lower_bound-1)
it = arrs[i].lower_bound(cur_time);
if(it != arrs[i].begin()){ // if there is indeed something below...
it--;
val = *it;
lower_goto= goes_to[i][val];
} else{
lower_goto= 0;
}
arrs[i].insert(cur_time);
previous_time = cur_time;
cur_time = max(lower_goto, cur_time+cur_speed*(s[i+1]-s[i]));
derr<<"$ cur_time = "<<cur_time<<"\n";
derr<<"$ previous_time = "<<previous_time<<"\n";
// below line causes issues (!)
if(goes_to[i].find(previous_time) != goes_to[i].end()){
derr<<"$ if..\n";
goes_to[i][previous_time] = max(goes_to[i][previous_time], cur_time);
} else{
derr<<"$ else..\n";
goes_to[i][previous_time] = cur_time;
}
}
}
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<<"running into any of these will make you goto: "<<goes_to[i][*it]<<"\n";
cerr<<"\n";
}
cerr<<"\n";
}
}
return;
}
long long arrival_time(long long Y){
ll cur_time = Y;
ll cur_speed = x;
ll lower_goto, val;
for(int i=0; i<m-1; i++){
it = arrs[i].lower_bound(cur_time);
if(it != arrs[i].begin()){ // if there is indeed something below...
it--;
val = *it;
lower_goto= goes_to[i][val];
} else{
lower_goto= 0;
}
cur_time = max(lower_goto, cur_time+cur_speed*(S[i+1]-S[i]));
}
return cur_time;
}
