#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, x;
vector<int> w, s;
vector<vector<long long>> when;
set<array<long long, 3>> res;
void init(int l, int N, vector<long long> t, vector<int> W, int X, int M, vector<int> S) {
n = N; m = M; x = X; w = W; s = S;
when = vector<vector<long long>>(m, vector<long long>(n));
when[0] = t;
for (int i = 1; i < m; i++) {
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
if (when[i - 1][a] != when[i - 1][b]) {
return when[i - 1][a] < when[i - 1][b];
} else {
return w[a] < w[b];
}
});
long long mx = 0;
for (int j = 0; j < n; j++) {
int b = order[j];
mx = max(mx, when[i - 1][b] + w[b] * 1LL * (s[i] - s[i - 1]));
when[i][b] = mx;
}
}
const long long inf = (long long) 1e18;
set<array<long long, 3>> st;
long long ft = 0;
set<pair<long long, long long>> id;
id.insert({inf, 0});
auto Update = [&](long long L, long long R, long long val) {
L = max(0LL, L);
if (L > R) {
return;
}
long long from = inf + 1, to = -1;
while (true) {
auto it = st.lower_bound({L, -1, -1});
if (it == st.end() || (*it)[0] > R) {
break;
}
long long l = (*it)[1], r = (*it)[2];
st.erase(it);
from = min(from, l);
to = max(to, r);
}
{
auto it = id.lower_bound({L, -1});
if (it != id.end()) {
long long pt = max(L, it->second);
if (pt >= it->second && pt <= it->first) {
from = min(from, pt);
}
}
}
{
auto it = id.lower_bound({R, -1});
if (it == id.end() || it->second > R) {
if (it != id.begin()) {
it = prev(it);
}
}
if (it != id.end()) {
long long pt = min(R, it->first);
if (pt >= it->second && pt <= it->first) {
to = max(to, pt);
}
}
}
if (from > to) {
return;
}
while (true) {
auto it = id.lower_bound({from, -1});
if (it == id.end() || it->second > to) {
break;
}
long long l = it->second, r = it->first;
id.erase(it);
if (l < from) {
id.insert({from - 1, l});
}
if (r > to) {
id.insert({r, to + 1});
}
}
st.insert({val, from, to});
};
for (int i = 1; i < m; i++) {
long long prv = ft;
ft += (s[i] - s[i - 1]) * 1LL * x;
vector<array<long long, 3>> ev;
for (int j = 0; j < n; j++) {
if (w[j] <= x) {
continue;
}
long long L = when[i][j] - w[j] * 1LL * (s[i] - s[i - 1]) + 1, R = when[i][j] - x * 1LL * (s[i] - s[i - 1]);
if (L > R) {
continue;
}
ev.push_back({L, R + 1, when[i][j]});
}
vector<long long> xs;
for (auto& p : ev) {
xs.push_back(p[0]);
xs.push_back(p[1]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
int sz = (int) xs.size();
vector<vector<long long>> qs(sz);
for (auto& p : ev) {
{
int idx = (int) (lower_bound(xs.begin(), xs.end(), p[0]) - xs.begin());
qs[idx].push_back(p[2]);
}
{
int idx = (int) (lower_bound(xs.begin(), xs.end(), p[1]) - xs.begin());
qs[idx].push_back(~p[2]);
}
}
vector<array<long long, 3>> segs;
{
multiset<long long> st;
for (int j = 0; j + 1 < sz; j++) {
for (auto& v : qs[j]) {
if (v >= 0) {
st.insert(v);
} else {
st.erase(st.find(~v));
}
}
if (!st.empty()) {
segs.push_back({xs[j] - prv, xs[j + 1] - 1 - prv, *prev(st.end()) - ft});
}
}
}
reverse(segs.begin(), segs.end());
for (auto& p : segs) {
Update(p[0], p[1], p[2]);
}
}
for (auto& p : st) {
res.insert({p[2], p[1], p[0]});
}
return;
}
long long arrival_time(long long y) {
auto it = res.lower_bound({y, -1, -1});
if (it != res.end() && (*it)[1] <= y) {
y = (*it)[2];
}
return y + s.back() * 1LL * x;
}
