#include "overtaking.h"
#include <algorithm>
#include <iostream>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
using namespace std;
ll L, n, x, m;
vector<ll> leave;
vector<ll> speed;
vector<ll> stat;
vector<vector<ll>> t;
vector<vector<ll>> ord;
void simulate(){
for (ll i=0; i<m; i++){
for (ll j=0; j<n; j++){
ord[i][j]=j;
}
}
for (ll i=0; i<n; i++){
t[0][i]=leave[i];
}
sort(ord[0].begin(), ord[0].end(), [&](ll bus1, ll bus2)->bool{
if (t[0][bus1]!=t[0][bus2]) return t[0][bus1]<t[0][bus2];
return speed[bus1]<speed[bus2];
});
for (ll i=1; i<m; i++){
for (ll j=0; j<n; j++){
t[i][j]=t[i-1][j]+speed[j]*(stat[i]-stat[i-1]);
}
for (ll j=1; j<n; j++){
t[i][ord[i-1][j]]=max(t[i][ord[i-1][j]], t[i][ord[i-1][j-1]]);
}
sort(ord[i].begin(), ord[i].end(), [&](ll bus1, ll bus2)->bool{
if (t[i][bus1]!=t[i][bus2]) return t[i][bus1]<t[i][bus2];
return speed[bus1]<speed[bus2];
});
}
}
void init(int _L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
L=_L; n=N; x=X; m=M;
t.resize(m, vector<ll>(n));
ord.resize(m, vector<ll>(n));
leave = T;
leave.push_back(0);
speed.resize(n);
stat.resize(m);
for (ll i=0; i<n; i++) {speed[i]=W[i];}
for (ll i=0; i<m; i++) {stat[i]=S[i];}
simulate();
// for (ll i=0; i<m; i++){
// for (ll j=0; j<n; j++) cout << t[i][j] << " ";
// cout << ln;
// }
}
long long arrival_time(long long Y)
{
// return 0;
ll time=Y, ordi;
ll l=-1, r=n;
while (l+1<r){
ll mid = (l+r)/2;
if (t[0][ord[0][mid]]>time or (t[0][ord[0][mid]]==time and speed[ord[0][mid]]>=x)) r=mid;
else l=mid;
}
ordi=r;
// return ordi;
for (ll i=1; i<m; i++){
time += (stat[i]-stat[i-1])*x;
if (ordi) time = max(time, t[i][ord[i][ordi-1]]);
l=-1, r=ordi;
while (l+1<r){
ll mid = (l+r)/2;
if (t[i][ord[i][mid]]>time or (t[i][ord[i][mid]]==time and speed[ord[i][mid]]>=x)) r=mid;
else l=mid;
}
ordi=r;
}
return time;
}
