#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Each element: [start, end], ordered by start then end.
using Seg = array<ll, 2>;
static ll gX, gL;
static set<Seg> mp; // global envelope after all stations
void init(int L, int N, std::vector<long long> T, std::vector<int> W,
int X, int M, std::vector<int> S) {
gX = X;
gL = L;
mp.clear();
// traj[j] stores per-segment constraints for reduced time across segment j -> j+1
// represented as pairs (start_reduced_at_station_j, end_reduced_at_station_{j+1})
vector< set<Seg> > traj(max(0, M - 1));
// Only buses slower than reserve (W[i] > X) can block it.
// Let w = W[i] - X, then reduced time increases by w * distance.
vector<Seg> buses;
buses.reserve(N);
for (int i = 0; i < N; i++) {
if ((ll)W[i] > gX) {
buses.push_back({(ll)W[i] - gX, T[i]}); // [w, start_time_at_airport]
}
}
// Process buses in descending w (slowest-first in reduced-slope sense).
sort(buses.begin(), buses.end());
reverse(buses.begin(), buses.end());
for (auto &bt : buses) {
ll w = bt[0];
ll cur = bt[1]; // reduced time at station 0 (since S[0]=0)
for (int j = 0; j < M - 1; j++) {
ll d = (ll)S[j + 1] - S[j];
ll nxt = cur + d * w; // expected reduced arrival if not blocked by even slower buses
// If there exists an already-processed (slower) bus with start < cur,
// then this bus's reduced arrival becomes at least that bus's reduced arrival.
auto it = traj[j].lower_bound({cur, (ll)-4e18});
if (it != traj[j].begin()) {
nxt = max(nxt, (*prev(it))[1]);
}
traj[j].insert({cur, nxt});
cur = nxt;
}
}
// Merge segments from last to first into mp (overall envelope).
// Maintain mp as an increasing-start, increasing-end envelope, pruning dominated entries.
for (int j = M - 2; j >= 0; j--) {
for (auto &se : traj[j]) {
ll s = se[0], e = se[1];
// Compose with already-built envelope on the suffix (j+1..end):
// if reduced time after this segment is e, it may be further pushed up by mp.
auto it = mp.lower_bound({e, (ll)-4e18});
if (it != mp.begin()) e = max(e, (*prev(it))[1]);
// Insert (s -> e) into mp, removing dominated intervals.
it = mp.lower_bound({s, (ll)-4e18});
while (it != mp.end() && (*it)[1] <= e) {
it = mp.erase(it);
}
mp.insert({s, e});
}
}
}
long long arrival_time(long long Y) {
// Work in reduced time at station 0: R0 = Y.
// Push it up using mp envelope.
auto it = mp.lower_bound({Y, (ll)-4e18});
if (it != mp.begin()) {
Y = max(Y, (*prev(it))[1]);
}
// Convert reduced time back to real time at hotel:
// t = R + X * L
return Y + gX * gL;
}
