#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF = 1LL<<61;
int n,m;
int x;
int l;
vector<int> s; // where the sorting stations are
vector<int> t; // leaving times
vector<int> w; //speeds
vector<vector<int>> ET; //expected time
vector<vector<int>> sorted_by_i; //ETs, sorted by the ith station
vector<vector<int>> sorted_by_minus_one; //ETs, sorted by the previous station
vector<vector<int>> prefmax; //prefix maximums of sorted by minus one
vector<map<int,int>> cache;
void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed X, signed M, std::vector<signed> S) {
s=vector<int>(S.begin(),S.end());
t=T;
w=vector<int>(W.begin(),W.end());
n=N;
l=L;
m=M;
x=X;
cache.resize(m);
ET=sorted_by_i=sorted_by_minus_one=vector<vector<int>>(M,vector<int>(N,0)); //the ET of each bus at each sorting station
prefmax=vector<vector<int>>(m,vector<int>(n+1,0));
for (int i=0; i<N; i++) {
ET[0][i] = t[i];
sorted_by_i[0][i] = i;
}
for (int j=1; j<m; j++) {
int delta = s[j]-s[j-1];
for (int i=0; i<n; i++) {
ET[j][i] = ET[j-1][i]+w[i]*delta;
}
for (int i=0; i<n; i++) {
for (int i1=0; i1<n; i1++) {
if (ET[j-1][i]>ET[j-1][i1]) {
ET[j][i] = max(ET[j][i],ET[j][i1]);
}
}
}
}
for (int j=0; j<m; j++) {
for (int i=0; i<n; i++) {
sorted_by_i[j][i] = sorted_by_minus_one[j][i] = i;
}
}
for (int j=0; j<m; j++) {
sort(sorted_by_i[j].begin(), sorted_by_i[j].end(),[&](const int i1, const int i2) {
return ET[j][i1]<ET[j][i2];
});
if (j>0) {
sort(sorted_by_minus_one[j].begin(), sorted_by_minus_one[j].end(),[&](const int i1, const int i2) {
return ET[j-1][i1]<ET[j-1][i2];
});
}
}
for (int j=1; j<m; j++) {
int ma = 0;
for (int i=0; i<n; i++) {
prefmax[j][i] = ma;
ma=max(ma,ET[j][sorted_by_minus_one[j][i]]);
}
prefmax[j][n] = ma;
}
return;
}
set<pair<int,int>> known;
long long arrival_time(long long Y) {
vector<int> states(m);
for (int j=1; j<m; j++) {
if (cache[j].count(Y)) return cache[j][Y];
states[j] = Y;
int delta = s[j]-s[j-1];
int prevy = Y;
Y+=delta*x;
//cout << j <<" " << delta <<" " << x << " " << Y << endl;
int l = 0;
int r = n;
while (l<r) {
int m = (l+r)/2;
int val = ET[j-1][sorted_by_minus_one[j][m]];
if (val<prevy) {
//need higher val
l=m+1;
}
else {
//need lower val
r=m;
}
}
//this is the number of values that matter, plus 1
int maval = prefmax[j][l];
Y=max(Y,maval);
}
for (int i=1; i<m; i++) {
cache[i][states[i]] = Y;
}
return Y;
}
