#include "overtaking.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, int> pi;
struct SegTree {
int size;
vector<ll> tree;
void init(int N) {
size = 1;
while (size < N) {
size *= 2;
}
tree.assign(2 * size, 0);
}
void set(int i, ll v, int x, int lx, int rx) {
if (lx == rx - 1) {
tree[x] = max(tree[x], v);
return;
}
int mid = (lx + rx) / 2;
if (i < mid) {
set(i, v, 2 * x + 1, lx, mid);
}
else {
set(i, v, 2 * x + 2, mid, rx);
}
tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
}
void set(int i, ll v) {
set(i, v, 0, 0, size);
}
ll get(int l, int r, int x, int lx, int rx) {
if (l >= rx || lx >= r) {
return 0;
}
else if (l <= lx && rx <=r) {
return tree[x];
}
int mid = (lx + rx) / 2;
ll g1 = get(l, r, 2 * x + 1, lx, mid);
ll g2 = get(l, r, 2 * x + 2, mid, rx);
return max(g1, g2);
}
ll get(int l, int r) {
return get(l, r, 0, 0, size);
}
};
int N, M, X;
// dp[i][j]: Arrival time of bus i to station j
vector<vector<ll>> dp;
vector<vector<ll>> times;
vector<SegTree> arrivals;
vector<int> S, W;
bool stationsort(const pi& a, const pi& b)
{
if (a.first == b.first) {
return W[a.second] > W[b.second];
}
return a.first < b.first;
}
int lower(ll t, vector<ll>& v)
{
return lower_bound(v.begin(), v.end(), t) - v.begin();
}
void init(int L, int n, vector<ll> T, vector<int> w, int x, int m, vector<int> stations)
{
N = n;
M = m;
S = stations;
W = w;
X = x;
dp.resize(M, vector<ll>(N));
arrivals.resize(M);
times.resize(M, vector<ll>(N));
for (int i = 0; i < N; i++) {
dp[0][i] = T[i];
}
for (int s = 1; s < M; s++) {
// Move from station s - 1 to station s
vector<pi> order(N);
for (int i = 0; i < N; i++) {
order[i] = mp(dp[s - 1][i], i);
times[s][i] = dp[s - 1][i];
}
sort(times[s].begin(), times[s].end());
times[s].resize(unique(times[s].begin(), times[s].end()) - times[s].begin());
arrivals[s].init(times[s].size());
sort(order.begin(), order.end());
ll prv = 0;
for (int i = 0; i < N; i++) {
int bus = order[i].second;
ll expected = order[i].first + (ll)W[bus] * (S[s] - S[s - 1]);
dp[s][bus] = max(expected, prv);
prv = max(expected, prv);
arrivals[s].set(lower(dp[s - 1][bus], times[s]), dp[s][bus]);
}
}
return;
}
long long arrival_time(ll Y)
{
ll prv = Y;
for (int s = 1; s < M; s++) {
ll expected = prv + (ll)X * (S[s] - S[s - 1]);
expected = max(expected, arrivals[s].get(0, lower(prv, times[s])));
prv = expected;
}
return prv;
}
