#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> starts, speeds, stations;
vector<vector<pair<ll, int>>> expected;
vector<vector<ll>> expectedFind;
ll length, n, m, speed;
void calcLayer(int layer) {
vector<pair<ll, int>> &prev = expected[layer - 1], &cur = expected[layer];
sort(prev.begin(), prev.end(), [](const pair<ll, int> a, const pair<ll, int> b) {
if (a.first == b.first) return speeds[a.second] < speeds[b.second];
return a.first < b.first;
});
// ll prevReach = 0, prevArrive2 = 0, prevReach2 = 0, dist = stations[layer] - stations[layer - 1];
// for (auto &[arrive, idx] : prev) {
// ll curReach = arrive + speeds[idx] * dist;
// if (arrive == prevArrive2) curReach = max(curReach, prevReach);
// else curReach = max(curReach, prevReach2);
// cur.emplace_back(curReach, idx);
// expectedFind[layer][idx] = curReach;
// if (arrive == prevArrive2) prevReach2 = max(prevReach2, curReach);
// else prevReach = prevReach2, prevArrive2 = arrive, prevReach2 = curReach;
// }
ll prevReach = 0, dist = stations[layer] - stations[layer - 1];
for (auto &[arrive, idx] : prev) {
ll curReach = arrive + speeds[idx] * dist;
curReach = max(curReach, prevReach);
cur.emplace_back(curReach, idx);
expectedFind[layer][idx] = curReach;
prevReach = max(prevReach, curReach);
}
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
length = L;
m = M;
starts = T;
speed = X;
for (auto &i : W) {
// if (i <= speed) continue;
speeds.push_back(i);
}
n = speeds.size();
for (auto &i : S) stations.push_back(i);
expected.resize(m);
expected[0].resize(n);
expectedFind.resize(m, vector<ll>(n, 0));
for (int i = 0; i < n; ++i) expected[0][i] = {starts[i], i}, expectedFind[0][i] = starts[i];
for (int i = 1; i < m; ++i) calcLayer(i);
// for (int i = 0; i < m; ++i) {
// cout << "LAYER: " << i << endl;
// for (auto j : expected[i]) cout << j.first << ' ' << j.second << " ";
// cout << endl;
// for (auto j : expectedFind[i]) cout << j << ' ';
// cout << endl;
// }
}
long long arrival_time(long long Y)
{
if (n == 1) return (Y + speed * length);
ll cur = Y;
for (int i = 1; i < m; ++i) {
auto which = lower_bound(expected[i - 1].begin(), expected[i - 1].end(), make_pair(cur, -1));
if (which == expected[i - 1].begin()) return (cur + speed * (stations[m - 1] - stations[i - 1]));
int idx = prev(which)->second;
cur += speed * (stations[i] - stations[i - 1]);
cur = max(cur, expectedFind[i][idx]);
}
return cur;
}
