#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
using i32 = int32_t;
using pii = pair<int, int>;
struct Bus {
int time, inv_speed, id_bus;
auto operator<=>(const Bus&) const = default;
};
int ceildiv(int x, int y) {
assert(y > 0);
return (x+y-1)/y;
}
class DemiDroiteMgr {
const int pente_reserve;
vector<Bus> dds;
int nbDroites;
public:
DemiDroiteMgr(const vector<Bus> &__dds, int __pente_reserve) :
pente_reserve(__pente_reserve), dds(__dds) {
nbDroites = dds.size();
sort(dds.begin(), dds.end());
}
/// returns {ceil(dpos of next int), bus}
optional<pii> first_intersected_bus(int temps_reserve) {
optional<pii> best;
for (auto &dd : dds) {
if (dd.time < temps_reserve) {
assert(dd.inv_speed - pente_reserve > 0);
int cdpos = ceildiv(
temps_reserve - dd.time,
dd.inv_speed - pente_reserve
);
if (!best.has_value() || cdpos < best->first) {
best = {cdpos, dd.id_bus};
}
}
}
return best;
}
};
int nb_bus, nb_stations, inv_speed_reserve;
vector<Bus> initial_buses;
vector<int> stations;
void make_table();
void init(i32, i32 N, std::vector<long long> T, std::vector<i32> W, i32 X, i32, std::vector<i32> S)
{
for (int i = 0; i < N; ++i) {
if (W[i] > X)
initial_buses.push_back({T[i], W[i], i});
}
stations = vector<int>(S.begin(), S.end());
nb_bus = initial_buses.size(), nb_stations = stations.size();
inv_speed_reserve = X;
make_table();
}
vector<DemiDroiteMgr> help_find_next_intersection;
/// table[i_station][i_bus] = time at which the bus gets to the station
vector<vector<int>> table;
void make_table() {
auto push_row = [] (const vector<Bus> &cur_buses) {
table.push_back(vector<int>(nb_bus));
for (const auto &bus : cur_buses) {
table.back()[bus.id_bus] = bus.time;
}
help_find_next_intersection.emplace_back(cur_buses, inv_speed_reserve);
};
vector<Bus> cur_buses = initial_buses;
push_row(cur_buses);
for (int i_sta = 0; i_sta < nb_stations - 1; ++i_sta) {
int dis = stations[i_sta+1] - stations[i_sta];
sort(cur_buses.begin(), cur_buses.end());
int i_earlier = 0, max_earl = 0;
vector<Bus> nxt_buses;
for (int i_time = 0; i_time < nb_bus; ++i_time) {
const auto& [cur_time, inv_speed, id_bus] = cur_buses[i_time];
while (i_earlier < i_time && cur_buses[i_earlier].time < cur_time) {
max_earl = max(nxt_buses[i_earlier++].time, max_earl);
}
int nxt_time = max(cur_time + inv_speed * dis, max_earl);
nxt_buses.push_back({nxt_time, inv_speed, id_bus});
}
push_row(nxt_buses);
cur_buses = nxt_buses;
}
}
struct Position {
int station, time;
};
Position next_pos(Position cur) {
Position if_no_inter = {
nb_stations - 1,
cur.time + (stations.back() - stations[cur.station]) * inv_speed_reserve
};
auto nx = help_find_next_intersection[cur.station].first_intersected_bus(cur.time);
if (!nx.has_value())
return if_no_inter;
auto [ceil_delta_pos, crossed_bus] = *nx;
int ceil_abspos = stations[cur.station] + ceil_delta_pos;
auto it = lower_bound(stations.begin(), stations.end(), ceil_abspos);
Position nxt;
nxt.station = it - stations.begin();
if (nxt.station > nb_stations-1)
return if_no_inter;
nxt.time = table[nxt.station][crossed_bus];
return nxt;
}
long long arrival_time(long long dep_time_reserve) {
Position cur {0, dep_time_reserve};
while (cur.station != nb_stations-1) {
cur = next_pos(cur);
}
return cur.time;
}
