#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
using i32 = int32_t;
using pii = pair<int, int>;
constexpr int INF = 3e18;
struct Bus {
int time, inv_speed, id_bus;
auto operator<=>(const Bus&) const = default;
};
int ceildiv(int x, int y) {
return (x+y-1) / y;
}
int inv_speed_reserve;
struct Event {
int time;
bool is_add;
int i_dd;
auto operator<=>(const Event&) const = default;
};
class DemiDroiteMgr {
vector<Bus> dds;
int nbDroites;
vector<pii> flags;
public:
DemiDroiteMgr(const vector<Bus> &__dds, bool all_queries) : dds(__dds) {
nbDroites = dds.size();
sort(dds.begin(), dds.end());
vector<Event> events;
for (int i = 0; i < nbDroites; ++i) {
auto &cur = dds[i];
events.push_back({cur.time, true, i});
if (!all_queries) {
int b1 = INF, b2 = -1;
for (int j = 0; j < i; ++j) if (dds[j].time < dds[i].time) {
int n = dds[i].time - dds[j].time;
int d = dds[j].inv_speed - inv_speed_reserve;
int cqo = (n+d-1)/d;
if (cqo < b1) { b1 = cqo; b2 = j; }
}
if (b2 != -1)
flags.push_back({cur.time-1, b2});
continue;
}
int min_tdel = cur.time;
for (int pw = 1ll << 60; pw; pw /= 2) {
int tps = min_tdel + pw;
bool dominated = false;
for (int j = 0; j < i; ++j) {
if (eval(dds[j], tps) < eval(dds[i], tps))
dominated = true;
}
if (!dominated)
min_tdel += pw;
}
++min_tdel;
assert(cur.time < min_tdel);
if (min_tdel <= (int)(1e18))
events.push_back({min_tdel+1, false, i});
}
if (!all_queries) return;
sort(events.begin(), events.end());
multiset<int> dd_open;
for (auto &[time, is_add, i_dd] : events) {
if (is_add) {
dd_open.insert(i_dd);
} else {
dd_open.erase(dd_open.find(i_dd));
}
assert(!dd_open.empty());
flags.push_back({time, *dd_open.rbegin()});
}
}
int eval(const Bus &dd, int temps_reserve) {
assert(dd.time < temps_reserve);
return ceildiv(
temps_reserve - dd.time,
dd.inv_speed - inv_speed_reserve
);
}
/// returns ceil(dpos of next int)
int first_intersection(int temps_reserve) {
auto it = lower_bound(flags.begin(), flags.end(), pii {temps_reserve, -1});
if (it == flags.begin()) {
return INF;
}
auto &dd = dds[prev(it)->second];
return eval(dd, temps_reserve);
}
};
int nb_bus, nb_stations;
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) {
Bus bus {T[i], W[i], (int)initial_buses.size()};
initial_buses.push_back(bus);
}
}
stations = vector<int>(S.begin(), S.end());
nb_bus = initial_buses.size(), nb_stations = stations.size();
inv_speed_reserve = X;
make_table();
}
struct TimeVec {
int N;
vector<int> cur_t;
vector<int> max_pref_nxt_exclusive;
TimeVec(const vector<Bus> &cur_a, const vector<Bus> &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 + 2) + 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> tvecs;
vector<DemiDroiteMgr> help_next_inter;
/// 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;
}
bool all_queries = help_next_inter.empty();
help_next_inter.emplace_back(cur_buses, all_queries);
};
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});
}
tvecs.emplace_back(cur_buses, nxt_buses);
push_row(nxt_buses);
cur_buses = nxt_buses;
}
}
struct Position {
int station, time;
auto operator<=>(const Position&) const = default;
};
int reserve_time_travel(int i_s1, int i_s2) {
return (stations[i_s2] - stations[i_s1]) * inv_speed_reserve;
}
Position next_pos(Position cur) {
Position no_inter = {
nb_stations - 1,
cur.time + reserve_time_travel(cur.station, nb_stations-1)
};
int ceil_delta_pos = help_next_inter[cur.station].first_intersection(cur.time);
if (ceil_delta_pos == INF)
return no_inter;
int ceil_abspos = stations[cur.station] + ceil_delta_pos;
auto it = lower_bound(stations.begin(), stations.end(), ceil_abspos);
if (it == stations.end())
return no_inter;
Position nxt;
nxt.station = it - stations.begin(); // after conflict
int before_conflict = nxt.station - 1;
int time_at_bef = cur.time + reserve_time_travel(cur.station, before_conflict);
nxt.time = tvecs[before_conflict].max_strict_below(time_at_bef);
assert(nxt.time >= reserve_time_travel(cur.station, nxt.station));
return nxt;
}
map<Position, int> dp;
vector<Position> seen;
long long arrival_time(long long dep_time_reserve) {
Position cur {0, dep_time_reserve};
seen.clear();
while (cur.station != nb_stations-1) {
if (dp.contains(cur)) {
cur.time = dp[cur];
break;
}
seen.push_back(cur);
cur = next_pos(cur);
}
for (Position &pos : seen)
dp[pos] = cur.time;
return cur.time;
}
