// E. Overtaking
#include<bits/stdc++.h>
#include "overtaking.h"
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
template<typename T>
using vv_t = vector<vector<T>>;
vv_t<long long> neArT;
vv_t<pair<long long, int>> arT;
vector<long long> s;
vector<long long> w;
long long x;
struct Val {
long long en, s, e;
};
bool operator<(const Val& l, const Val& r) {
return l.e < r.e;
}
bool operator==(const Val& l, const Val& r){
return tie(l.s, l.e, l.en) == tie(r.s, r.e, r.en);
}
vv_t<Val> backT;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
// init arT amd neArT
vector<bool> val(N, true);
int nn = N;
for (int i = 0; i < N; ++i) {
if (W[i] <= X) {
val[i] = false;
nn--;
}
}
N = nn;
assert(N * M <= 1e5);
arT = vv_t<pair<long long, int>>(M - 1, vector<pair<long long, int>>(N));
neArT = vv_t<long long>(M - 1, vector<long long>(N));
backT = vv_t<Val>(M);
for (int i = 0; i < M; ++i) {
backT[i].reserve(2*N);
}
x = X;
s = vector<long long>(S.begin(), S.end());
w = vector<long long>(N);
vector<long long> t(N);
int ind = 0;
for (int i = 0; i < W.size(); ++i) {
if (val[i]) {
t[ind] = T[i];
w[ind++] = W[i];
}
}
vector<int> o(N);
std::iota(o.begin(), o.end(), 0);
std::sort(o.begin(), o.end(), [&](int l, int r) { return tie(t[l], w[l]) < tie(t[r], w[r]); });
for (int i = 0; i < N; ++i) {
arT[0][i] = {t[o[i]], o[i]};
neArT[0][i] = t[o[i]] + w[o[i]] * (s[1] - s[0]);
if (i > 0) neArT[0][i] = max(neArT[0][i], neArT[0][i - 1]);
}
// for each M
for (int i = 1; i < M - 1; ++i) {
// sort bus according to departure first, speed second
std::sort(o.begin(), o.end(),
[&](int l, int r) {
return tie(neArT[i - 1][l], w[arT[i - 1][l].second]) <
tie(neArT[i - 1][r], w[arT[i - 1][r].second]);
});
// go through sorted and compute next arrival time, keep max of others
for (int j = 0; j < N; ++j) {
arT[i][j] = {neArT[i - 1][o[j]], arT[i - 1][o[j]].second};
// make a prefix max array of the next arrival time
neArT[i][j] = arT[i][j].first + w[arT[i][j].second] * (s[i + 1] - s[i]);
if (j > 0) neArT[i][j] = max(neArT[i][j], neArT[i][j - 1]);
}
}
// go backwards, have the intervals where stuff happens.
for (int i = 0; i < N; ++i) {
backT.back().push_back({neArT.back()[i], neArT.back()[i], neArT.back()[i]});
}
std::sort(backT.back().begin(), backT.back().end());
backT.back().erase(std::unique(backT.back().begin(), backT.back().end()), backT.back().end());
for (int i = M - 2; i >= 0; --i) {
vector<Val> ne(backT[i + 1].size());
for (int j = 0; j < ne.size(); ++j) {
ne[j].en = backT[i + 1][j].en;
ne[j].e = backT[i + 1][j].e - X*(s[i + 1] - s[i]);
ne[j].s = backT[i + 1][j].s - X*(s[i + 1] - s[i]);
}
for (int j = 0; j < N; ++j) {
long long pos = neArT[i][j];
int neP = std::lower_bound(backT[i + 1].begin(), backT[i + 1].end(), pos,
[&](Val l, long long r) { return l.e < r;}) - backT[i + 1].begin();
if (backT[i + 1][neP].s <= pos) ne[neP].s = min(ne[neP].s, arT[i][j].first + 1);
}
int neS = ne.size();
for (int j = 0; j < N; ++j) {
long long oP = arT[i][j].first;
int neO = std::lower_bound(ne.begin(), ne.begin() + neS, oP,
[&](Val l, long long r) { return l.e < r;}) - ne.begin();
if (ne[neO].s > oP) ne.push_back({oP + x*(s.back() - s[i]), oP, oP});
}
std::sort(ne.begin(), ne.end());
ne.erase(std::unique(ne.begin(), ne.end()), ne.end());
long long last;
if (!ne.empty()) {
backT[i].push_back(ne.back());
last = ne.back().s;
}
for (int j = ne.size() - 2; j >= 0; --j) {
ne[j].e = min(ne[j].e, last - 1);
last = min(last, ne[j].s);
if (ne[j].e >= ne[j].s) {
backT[i].push_back(ne[j]);
}
}
std::reverse(backT[i].begin(), backT[i].end());
}
}
long long arrival_time(long long Y) {
int neP = std::lower_bound(backT.front().begin(), backT.front().end(), Y,
[&](Val l, long long r) { return l.e < r;}) - backT.front().begin();
if (neP < backT.front().size() && backT.front()[neP].s <= Y) return backT.front()[neP].en;
return Y + x*(s.back() - s.front());
}
//502032794
