#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 1005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int T[MAXN][MAXN];
int n;
int m;
int xt;
vector<int32_t>S;
vector<pi> nxt[MAXN]; // nxt[t] -> {time at this station, time at next station}
void init(int32_t L, int32_t n, std::vector<long long> tt, std::vector<int32_t> W, int32_t X, int32_t m, std::vector<int32_t> S)
{
::S=S;
xt=X;
::n=n;
::m=m;
// compute arrival times of each bus at each station
for(int x=0;x<n;x++){
T[x][0]=tt[x];
}
for(int t=1;t<m;t++){
vector<pi> vec;
for(int x=0;x<n;x++){
vec.push_back({T[x][t-1],x});
}
sort(vec.begin(),vec.end());
int idx=0;
int mx=0;
for(int x=0;x<n;x++){
int xidx=vec[x].second;
while(idx<n && vec[idx].first<T[xidx][t-1]){
int idxidx=vec[idx].second;
int exp=T[idxidx][t-1] + (int)W[idxidx] * (int)(S[t]-S[t-1]);
mx=max(mx,exp);
++idx;
}
int ex=T[xidx][t-1] + (int)W[xidx] * (int)(S[t]-S[t-1]);
T[xidx][t]=max(mx,ex);
}
}
for(int t=0;t<m-1;t++){
for(int x=0;x<n;x++){
nxt[t].push_back({T[x][t],T[x][t+1]});
}
sort(nxt[t].begin(),nxt[t].end(),[](pi x, pi y){
if(x.first != y.first)return x.first <y.first;
else return x.second>y.second;//we only want to keep the biggest next of the same timing
});
bool need[n+5];memset(need,0,sizeof need);
int mx=-oo;
for(int x=0;x<n;x++){
if(nxt[t][x].second > mx){
mx=nxt[t][x].second;
need[x]=1;
}
}
vector<pi>res;
for(int x=0;x<n;x++){
if(need[x])res.push_back(nxt[t][x]);
}
nxt[t]=res;
}
}
long long arrival_time(long long Y)
{
for(int t=1;t<m;t++){
int exp=Y + xt * (int)(S[t]-S[t-1]);
auto it=lower_bound(nxt[t-1].begin(),nxt[t-1].end(),make_pair(Y,-oo));
if(it != nxt[t-1].begin()){
exp=max(exp,prev(it)->second);
}
Y=exp;
}
return Y;
}
