#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using tlli = tuple<ll, ll, int>;//prev time, next time, index
using tll = tuple<ll, ll>;
const ll INF = 3'123'456'123'456'123'456;
ll L;
int N;
vector<ll> T;
vector<ll> W;
ll X;
int M;
vector<ll> S;
vector<vector<ll>> times;
vector<vector<tll>> range_map;
void init(int L1, int N1, std::vector<long long> T1, std::vector<int> W1, int X1, int M1, std::vector<int> S1)
{
L = L1;
N = N1;
T = T1;
for (int i: W1)
W.push_back(i);
X = X1;
W.push_back(X);
M = M1;
for (int i: S1)
S.push_back(i);
times = vector<vector<ll>> (N+1);
for (int i=0; i<N; i++)
times[i].push_back(T[i]);
for (int sorting = 1; sorting<M; sorting++)
{
ll length = S[sorting] - S[sorting-1];
vector<tlli> move;
for (int i=0; i<N; i++)
{
move.push_back({times[i][sorting-1], times[i][sorting-1] + (length*W[i]), i});
}
sort(move.begin(), move.end());
ll running_max = -1;
for (int j=0; j<N; j++)
{
running_max = max(running_max, get<1>(move[j]));
int i = get<2>(move[j]);
times[i].push_back(running_max);
}
}
for (int sorting = 1; sorting<M; sorting++)
{
vector<tll> rang;
for (int i=0; i<N; i++)
rang.push_back({times[i][sorting-1], times[i][sorting]});
rang.push_back({INF, INF});
rang.push_back({-1, 0});
sort(rang.begin(), rang.end());
range_map.push_back(rang);
}
}
long long arrival_time(long long Y)
{
ll curr = Y;
for (int sorting = 1; sorting<M; sorting++)
{
ll expected = ((S[sorting]-S[sorting-1])*X)+curr;
int lo = 0;
int hi = N+1;
while (lo!=hi)
{
int mid = (lo+hi)/2;
if (get<0>(range_map[sorting-1][mid]) >= curr)
hi = mid;
else
lo = mid+1;
}
expected = max(expected, get<1>(range_map[sorting-1][lo-1]));
curr = expected;
}
return curr;
}
