#include "overtaking.h" #include <bits/stdc++.h> using namespace std; using ll = long long; int MT,XT; vector<int>ST(1005); set<pair<ll,ll>>st[1005]; void init(int L,int N,vector<ll> T,vector<int> W,int X,int M,vector<int> S){ for(int i=0;i<M;i++)ST[i]=S[i]; MT=M,XT=X; vector<pair<ll,int>>tw(N); for(int i=0;i<N;i++)tw[i]={T[i],W[i]}; sort(tw.begin(),tw.end()); for(int i=1;i<M;i++){ ll t=-1,mp=0,la=0,lan=0; vector<pair<ll,int>>ntw(N); for(int j=0;j<N;j++){ if(t==-1)t=tw[j].first; if(t<tw[j].first){ la=max(la,lan); st[i-1].insert({t,la}); t=tw[j].first; } ntw[j]={max(tw[j].first+tw[j].second*(S[i]-S[i-1]),mp),tw[j].second}; mp=max(mp,ntw[j].first); lan=max(lan,ntw[j].first); } la=max(la,lan); st[i-1].insert({t,la}); swap(tw,ntw); sort(tw.begin(),tw.end()); } return; } long long arrival_time(long long Y){ for(int i=0;i<MT-1;i++){ auto r=st[i].lower_bound({Y,0}); ll d=Y+XT*(ST[i+1]-ST[i]); if(r==st[i].begin())Y=d; else{ r--; Y=max(d,(*r).second); } } return Y; }