#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long un;
typedef vector<un> vuc;
typedef tuple<un, un, un> tup;
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()
constexpr un INF = INT64_MAX;
vec<vuc> prij;
vec<vuc> dalsi;
vec<vuc> goats;
vec<vec<tup>> seraz;
un speed;
vuc _S;
un _M;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
speed = X;
_S = vuc(M);
REP(i, 0, M) _S[i] = S[i];
vuc _W(N);
REP(i, 0, N) _W[i] = W[i];
_M = M;
prij = vec<vuc>(M, vuc(N, -1));
dalsi = vec<vuc>(M, vuc(N, -1));
goats = vec<vuc>(M, vuc(N, -1));
prij[0] = T;
REP(e, 0, M-1){
vec<tup> toSort;
REP(i, 0, N){
toSort.push_back({prij[e][i], _W[i], i});
}
sort(ALL(toSort));
seraz.push_back(toSort);
un limit = 0;
un nasl = -1;
un lastOdj = -1;
un lastIndex = -1;
REP(i, 0, N){
un odjezd, index;
tie(odjezd, ignore, index) = toSort[i];
if (lastOdj != odjezd) nasl = lastIndex;
limit = max(limit, odjezd + _W[index] * (_S[e+1] - _S[e]));
prij[e+1][index] = limit;
dalsi[e][index] = nasl;
lastOdj = odjezd;
lastIndex = index;
}
un vor = -1;
lastOdj = -1;
for(un i = N-1; i > -1; i--){
un odjezd, index;
tie(odjezd, ignore, index) = toSort[i];
if (lastOdj != odjezd) vor = index;
goats[e][index] = vor;
lastOdj = odjezd;
}
}
}
long long arrival_time(long long Y)
{
un now = Y;
tup what = {now, speed, -1};
un snek;
auto ptr = upper_bound(ALL(seraz[0]), what);
if (ptr == seraz[0].begin()){
return now + speed * (_S[_M-1] - _S[0]);
}
else{
ptr--;
tie(ignore, ignore, snek) = *ptr;
}
REP(e, 0, _M-1){
if (snek == -1){
return now + speed * (_S[_M-1] - _S[e]);
}
if (now + speed * (_S[e+1] - _S[e]) <= prij[e+1][snek]){
now = prij[e+1][snek];
snek = dalsi[e+1][snek];
}
else{
now = now + speed * (_S[e+1] - _S[e]);
snek = goats[e+1][snek];
}
}
return now;
}
