#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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, x;
vector<vector<tuple<ll, ll, ll>>> am; // t maar kan gesorteerd worden
vi s;
vector<vi> tmap;
vector<ii> intervals; // Als na t weggaat dan vertraging
void init(int32_t L, int32_t N, std::vector<long long> T, std::vector<int32_t> W, int32_t X, int32_t M, std::vector<int32_t> S)
{
set<ii> ends; // vertragingen die nog geen volgende hebben.
vi parent; // vertragingen vormen een tree (forest).
l = L;
x = X;
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);
set<ii> newends;
sort(all(arrived_map[j-1]));
ll mx = 0;
for(auto [prev_arrive_time, z, i]: arrived_map[j-1])
{
mx = max(mx, e[j][i]);
t[j][i] = mx;
if(z > x)
{
auto it = upper_bound(all(ends), ii{prev_arrive_time - S[j-1]*x, LONG_LONG_MAX});
while(it != ends.end() && it->first < mx - S[j]*x)
{
int index = it->second;
parent[index] = intervals.size();
ends.erase(it);
it = upper_bound(all(ends), ii{prev_arrive_time - S[j-1]*x, LONG_LONG_MAX});
}
intervals.emplace_back(prev_arrive_time - S[j-1]*x, mx - S[j]*x);
parent.push_back(-1);
newends.emplace(mx - S[j]*x, intervals.size() - 1);
}
}
for(auto i: newends)
ends.insert(i);
}
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;
for(int i = intervals.size() - 1; i >= 0; i--)
{
if(parent[i] != -1)
intervals[i].second = intervals[parent[i]].second;
}
sort(all(intervals));
for(int i = 1; i < intervals.size(); i++)
{
if(intervals[i-1].first == intervals[i].first)
{
intervals[i].second = max(intervals[i].second, intervals[i-1].second);
}
}
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]));
// }
auto it = lower_bound(all(intervals), ii{Y, 0});
if(it == intervals.begin())
return Y + l*x;
it--;
return max(it->second, Y) + l*x;
}
