#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> w, s;
vector<vector<long long>> t;
vector<vector<pair<long long, long long>>> ps;
void init(int L, int N_, vector<long long> T, vector<int> W, int X, int M_, vector<int> S) {
n = N_, m = M_;
w = W;
w.push_back(X);
s = S;
t.resize(m);
t[0] = T;
for (int j = 1; j < m; ++j) {
t[j].resize(n);
vector<long long> e(n);
for (int i = 0; i < n; ++i) {
e[i] = t[j - 1][i] + (long long) w[i] * (s[j] - s[j - 1]);
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
return t[j - 1][x] < t[j - 1][y];
});
int ptr = 0;
long long mx = 0;
for (int i = 0; i < n; ++i) {
int cur_bus = ord[i];
while (ptr < i && t[j - 1][ord[ptr]] < t[j - 1][cur_bus]) {
mx = max(mx, e[ord[ptr]]);
ptr++;
}
t[j][cur_bus] = max(e[cur_bus], mx);
}
//cout << "J: " << j << ' ';
//for (int i = 0; i < n; ++i) {
//cout << t[j][i] << " \n"[i == n - 1];
//}
}
ps.resize(m - 1);
for (int j = 0; j < m - 1; ++j) {
ps[j].resize(n);
for (int i = 0; i < n; ++i) {
ps[j][i] = {t[j][i], t[j + 1][i]};
}
sort(ps[j].begin(), ps[j].end());
for (int i = 1; i < n; ++i) {
ps[j][i].second = max(ps[j][i].second, ps[j][i - 1].second);
}
}
}
long long arrival_time(long long cur_time) {
for (int j = 1; j < m; ++j) {
long long e = cur_time + (long long) w[n] * (s[j] - s[j - 1]);
pair<long long, long long> key = {cur_time, 0LL};
int ind = lower_bound(ps[j - 1].begin(), ps[j - 1].end(), key) - ps[j - 1].begin() - 1;
long long block_time = 0;
if (ind >= 0) {
block_time = max(block_time, ps[j - 1][ind].second);
}
cur_time = max(e, block_time);
}
return cur_time;
}
