#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
using i32 = int32_t;
struct Bus {
int dep_time, inv_speed;
};
int nb_bus, nb_segments, inv_speed_reserve;
vector<Bus> buses;
vector<int> segments;
void make_table();
void init(i32, i32 N, std::vector<long long> T, std::vector<i32> W, i32 X, i32 M, std::vector<i32> S)
{
for (int i = 0; i < N; ++i) {
buses.push_back({T[i], W[i]});
}
for (int i = 0; i < M-1; ++i) {
segments.push_back(S[i+1] - S[i]);
}
nb_bus = buses.size(), nb_segments = segments.size();
inv_speed_reserve = X;
make_table();
}
struct Arrival {
int time, id_bus;
auto operator<=>(const Arrival&) const = default;
};
struct TimeVec {
int N;
vector<int> cur_t;
vector<int> max_pref_nxt_exclusive;
TimeVec(vector<Arrival> cur_a, vector<Arrival> nxt_a) : N(cur_a.size()) {
max_pref_nxt_exclusive.push_back(0);
for (int i = 0; i < N; ++i) {
cur_t.push_back(cur_a[i].time);
max_pref_nxt_exclusive.push_back(
max(max_pref_nxt_exclusive.back(), nxt_a[i].time)
);
}
}
/// returns the maximum of nxt(bus), among all buses such that cur(bus) < x
int max_strict_below(int x) {
const int lg = (int)log2(N) + 1;
int i = 0;
for (int pw = (1 << lg); pw; pw /= 2) {
if (i+pw <= N && cur_t[i+pw-1] < x)
i += pw;
}
return max_pref_nxt_exclusive[i];
}
};
vector<TimeVec> table;
void make_table()
{
vector<Arrival> cur_arrivals;
for (int iBus = 0; iBus < nb_bus; ++iBus) {
cur_arrivals.push_back({buses[iBus].dep_time, iBus});
}
for (int dis : segments) {
sort(cur_arrivals.begin(), cur_arrivals.end());
int i_earlier = 0, max_earl = 0;
vector<Arrival> nxt_arrivals;
for (int i_time = 0; i_time < nb_bus; ++i_time) {
auto& [cur_time, id_bus] = cur_arrivals[i_time];
int inv_speed = buses[id_bus].inv_speed;
while (i_earlier < i_time && cur_arrivals[i_earlier].time < cur_time) {
max_earl = max(nxt_arrivals[i_earlier++].time, max_earl);
}
int nxt_time = max(cur_time + inv_speed * dis, max_earl);
nxt_arrivals.push_back({nxt_time, id_bus});
}
table.emplace_back(cur_arrivals, nxt_arrivals);
cur_arrivals = nxt_arrivals;
}
}
long long arrival_time(long long dep_time_reserve) {
int cur_time = dep_time_reserve;
for (int i_segment = 0; i_segment < nb_segments; ++i_segment) {
int dis = segments[i_segment];
int max_earl = table[i_segment].max_strict_below(cur_time);
cur_time = max(cur_time + dis * inv_speed_reserve, max_earl);
}
return cur_time;
}
