#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<ll, ll> ii; // tijd, bus nummer
typedef vector<ii> vii; // tijden waarop bussen aankomen;
typedef vector<ll> vi;
ll l, d, x, m;
vector<vector<tuple<ll, ll, ll>>> am; // t maar kan gesorteerd worden
vi s;
vector<vi> tmap;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
l = L;
d = L - S[M-1];
x = X;
m = M;
s.insert(s.begin(), all(S));
vector<vector<tuple<ll, ll, ll>>> arrived_map(M); // t maar kan gesorteerd worden
vector<vi> t(M, vi(N)), e(M, vi(N)); // eigenlijke tijd (voor ieder sorteer-dinges), expected
for(int i = 0; i < N; i++)
{
t[0][i] = T[i];
}
for(int j = 1; j < M; j++)
{
ll distance = (S[j] - S[j-1]);
for(int i = 0; i < N; i++)
e[j][i] = t[j-1][i] + W[i]*distance;
for(int i = 0; i < N; i++)
arrived_map[j-1].emplace_back(t[j-1][i], W[i], i);
sort(all(arrived_map[j-1]));
ll mx = 0; // niet long max maar rij-tijd
for(auto [_, z, i]: arrived_map[j-1])
{
mx = max(mx, e[j][i]);
t[j][i] = mx;
}
}
for(int i = 0; i < N; i++)
arrived_map[M-1].emplace_back(t[M-1][i], W[i], i);
am = arrived_map;
tmap = t;
return;
}
long long arrival_time(long long Y)
{
ll t = Y;
for(int j = 1; j < m; j++)
{
auto it = lower_bound(all(am[j-1]), tuple{t, 0, 0});
if(it == am[j-1].begin())
{
t += x * (s[j] - s[j-1]);
continue;
}
it--;
//int i = it - am[j-1].begin() - 1;
t = max(tmap[j][get<2>(*it)], t + x * (s[j] - s[j-1]));
}
return t;
}
