#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inf = 1e9;
vector<vector<ll>> init_arrival_time;
vector<vector<pair<ll,ll>>> max_prefix_sroted_time;
vector<ll> t, w, s;
ll l, n,x, m;
vector<vector<ll>> get_arrivial_time(){
ll n = t.size();
vector<vector<ll>> ans(m, vector<ll>(n));
vector<vector<pair<ll,ll>>> sorted(m);
ans[0] = t;
// for(auto a:ans[0])cout<<a<<" ";
// cout<<endl;
for(int i=1; i<m; i++){
vector<pair<ll,ll>> vec;
for(int j=0; j<n; j++)vec.push_back({ans[i-1][j], j});
sort(vec.begin(), vec.end());
sorted[i-1] = vec;
ll cur_max = -inf, cur_max2 = -inf;
for(int j=0; j<n; j++){
ll val = vec[j].first + w[vec[j].second] * (s[i] - s[i-1]);
if(j and vec[j-1].first == vec[j].first){
val = max(val, cur_max2);
}
else {
cur_max2 = cur_max;
val = max(val, cur_max);
}
cur_max = max(val, cur_max);
ans[i][vec[j].second] = val;
}
// for(auto a:ans[i])cout<<a<<" ";
// cout<<endl;
}
vector<pair<ll,ll>> vec;
for(int j=0; j<n; j++)vec.push_back({ans[m-1][j], j});
sort(vec.begin(), vec.end());
sorted[m-1] = vec;
// for(auto a:sorted){
// for(auto b:a)cout<<"("<<b.first<<" , "<<w[b.second]<<") ";
// cout<<endl;
// }
max_prefix_sroted_time = sorted;
for(int i=0; i<m; i++){
for(int j=1; j<n; j++){
max_prefix_sroted_time[i][j].first = max(max_prefix_sroted_time[i][j].first, max_prefix_sroted_time[i][j-1].first);
}
}
// cout<<endl<<endl;
return ans;
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
t = T;
l = L;
n = N;
x = X;
m = M;
w = vector<ll>(n);
for(int i=0; i<n; i++)w[i] = W[i];
s = vector<ll>(m);
for(int i=0; i<m; i++)s[i] = S[i];
init_arrival_time = get_arrivial_time();
return;
}
long long arrival_time(long long Y)
{
for(int i=0; i<m-1; i++){
ll l=0, r = n-1;
while(l<=r){
ll mid = l + (r-l)/2;
if(max_prefix_sroted_time[i][mid].first < Y) l=mid+1;
else r=mid-1;
}
Y = max(Y + x * (s[i+1] - s[i]), (r==-1?-inf:max_prefix_sroted_time[i+1][r].first));
}
return Y;
}
