// 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<long long> arT;
vector<long long> s;
vector<long long> w;
vv_t<long long> backT;
long long x;
struct Val {
long long en, s, e;
};
bool operator<(const Val& l, const Val& r) {
return l.e < r.e;
}
vector<Val> resV;
int wij(int i, int j, int p) {
int l = p - 1, r = s.size();
while (l + 1 < r){
int m = (l + r)/2;
if (arT[p][i] + w[i]*(s[m] - s[p]) > arT[p][j] + w[j]*(s[m] - s[p])) r = m;
else l = m;
}
return l;
}
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;
arT = vv_t<long long>(M - 1, vector<long long>(N));
neArT = vv_t<long long>(M - 1, vector<long long>(N));
backT = vv_t<long long>(M, vector<long long>(N));
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][o[i]] = t[o[i]];
neArT[0][o[i]] = t[o[i]] + w[o[i]] * (s[1] - s[0]);
if (i > 0) neArT[0][o[i]] = max(neArT[0][o[i]], neArT[0][o[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[l]) <
tie(neArT[i - 1][r], w[r]);
});
// go through sorted and compute next arrival time, keep max of others
for (int j = 0; j < N; ++j) {
arT[i][o[j]] = neArT[i - 1][o[j]];
// make a prefix max array of the next arrival time
neArT[i][o[j]] = arT[i][o[j]] + w[o[j]] * (s[i + 1] - s[i]);
if (j > 0) neArT[i][o[j]] = max(neArT[i][o[j]], neArT[i][o[j - 1]]);
}
}
for (int i = 0; i < N; ++i) {
backT.back()[i] = neArT.back()[i];
}
// sort by arT, w, and then do deque / convex hull opt to find the
// find cutting point, by binary search on M
for (int i = M - 2; i >= 0; --i) {
std::sort(o.begin(), o.end(),
[&](int l, int r) {
return tie(arT[i][l], w[l]) <
tie(arT[i][r], w[l]);
});
deque<pair<int,int>> st;
for (int j = 0; j < N; ++j) {
int po = o[j];
if (j > 0 && arT[i][po] == arT[i][o[j - 1]]) {
backT[i][po] = backT[i][o[j - 1]];
} else {
int l = -1, r = st.size();
while (l + 1 < r) {
int m = (l + r)/2;
if (arT[i][po] + x*(s[st[m].second] - s[i]) < arT[i][st[m].first]+ w[st[m].first]*(s[st[m].second] - s[i])) r = m;
else l = m;
}
if (r == st.size()) {
backT[i][po] = arT[i][po] + x*(s.back() - s[i]);
} else {
int ll = i, rr = st[r].second;
if (r > 0) {
ll = st[r - 1].second;
}
while (ll + 1 < rr) {
int mm = (ll + rr)/2;
if (arT[i][po] + x*(s[mm] - s[i]) < arT[i][st[r].first]+ w[st[r].first]*(s[mm] - s[i])) rr = mm;
else ll = mm;
}
backT[i][po] = backT[rr][st[r].first];
}
}
while (!st.empty() && wij(st.back().first, po, i) >= st.back().second) st.pop_back();
if (!st.empty()) st.push_back({po, wij(st.back().first, po, i)});
else st.push_back({po, M - 1});
if (st.back().second <= i) st.pop_back();
}
}
// fill in last line by looking at each highest point in order.
std::sort(o.begin(), o.end(),
[&](int l, int r) {
return tie(arT[0][l], w[l]) <
tie(arT[0][r], w[r]);
});
deque<pair<int,int>> st;
for (int i = 0; i < N; ++i) {
int po = o[i];
int last = 0;
while (!st.empty() && wij(st.back().first, po, 0) >= st.back().second) {
for (int j = last + 1; j <= st.back().second; ++j) {
if (arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1 > arT[0][po]) break;
resV.push_back({backT[j][st.back().first], arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1, min(arT[0][st.back().first] + (w[st.back().first] - x)*(s[j] - s[0]), arT[0][po])});
}
last = st.back().second;
st.pop_back();
}
if (!st.empty()) {
for (int j = last + 1; j <= wij(st.back().first, po, 0); ++j) {
if (arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1 > arT[0][po]) break;
resV.push_back({backT[j][st.back().first], arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1, min(arT[0][st.back().first] + (w[st.back().first] - x)*(s[j] - s[0]), arT[0][po])});
}
st.push_back({po, wij(st.back().first, po, 0)});
}
else st.push_back({po, M - 1});
if (st.back().second <= 0) st.pop_back();
}
int last = 0;
while (!st.empty()) {
for (int j = last + 1; j <= st.back().second; ++j) {
resV.push_back({backT[j][st.back().first], arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1, arT[0][st.back().first] + (w[st.back().first] - x)*(s[j] - s[0])});
}
last = st.back().second;
st.pop_back();
}
}
long long arrival_time(long long Y) {
int neP = std::lower_bound(resV.begin(), resV.end(), Y,
[&](Val l, long long r) { return l.e < r;}) - resV.begin();
if (neP < resV.size() && resV[neP].s <= Y) return resV[neP].en;
return Y + x*(s.back() - s.front());
}
//502032794
