#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int l, n, x, m;
vector<ll> t;
vector<int> w, s;
ll est[1010][1010], arr[1010][1010];
pll range[1010][1010];
struct seg {
int sz;
vector<ll> vals;
ll tree[8080], lazy[8080];
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = -1;
lazy[v] = -1;
return;
}
int mid = (st + ed) / 2;
init(2 * v, st, mid);
init(2 * v + 1, mid + 1, ed);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
lazy[v] = -1;
}
void propagate(int v, int st, int ed) {
tree[v] = max(tree[v], lazy[v]);
if (st != ed) {
lazy[2 * v] = max(lazy[2 * v], lazy[v]);
lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
}
}
void update(int v, int st, int ed, int lt, int rt, ll val) {
propagate(v, st, ed);
if (lt > ed || rt < st) return;
if (lt <= st && ed <= rt) {
lazy[v] = max(lazy[v], val);
propagate(v, st, ed);
return;
}
int mid = (st + ed) / 2;
update(2 * v, st, mid, lt, rt, val);
update(2 * v + 1, mid + 1, ed, lt, rt, val);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
ll get(int v, int st, int ed, int idx) {
propagate(v, st, ed);
if (st > idx || ed < idx) return -1;
if (st == idx && ed == idx) return tree[v];
int mid = (st + ed) / 2;
return max(get(2 * v, st, mid, idx), get(2 * v + 1, mid + 1, ed, idx));
}
} sg[1010];
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
l = L; n = N; t = T; w = W; x = X; m = M; s = S;
for (int i = 0; i < n; i++) arr[0][i] = t[i];
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) est[j][i] = arr[j - 1][i] + (ll)w[i] * (s[j] - s[j - 1]);
vector<pll> tlist;
for (int i = 0; i < n; i++) tlist.push_back({arr[j - 1][i], i});
sort(tlist.begin(), tlist.end());
ll last = 0, p = 0;
for (int i = 0; i < n; i++) {
while (tlist[p].first < tlist[i].first) {
last = max(last, est[j][tlist[p].second]);
p++;
}
arr[j][tlist[i].second] = max(last, est[j][tlist[i].second]);
}
}
for (int j = 0; j < m - 1; j++) {
for (int i = 0; i < n; i++) {
if (w[i] > x) {
range[j][i] = {arr[j][i] + 1, arr[j][i] + (ll)(w[i] - x) * (s[j + 1] - s[j])};
sg[j].vals.push_back(range[j][i].first);
sg[j].vals.push_back(range[j][i].second);
}
}
sort(sg[j].vals.begin(), sg[j].vals.end());
sg[j].vals.erase(unique(sg[j].vals.begin(), sg[j].vals.end()), sg[j].vals.end());
sg[j].sz = sg[j].vals.size();
sg[j].init(1, 0, sg[j].sz);
for (int i = 0; i < n; i++) {
if (w[i] > x) {
int s = lower_bound(sg[j].vals.begin(), sg[j].vals.end(), range[j][i].first)
- sg[j].vals.begin() + 1;
int e = lower_bound(sg[j].vals.begin(), sg[j].vals.end(), range[j][i].second)
- sg[j].vals.begin() + 1;
sg[j].update(1, 0, sg[j].sz, s, e - 1, arr[j + 1][i]);
}
}
}
return;
}
ll arrival_time(ll Y) {
ll y = Y;
for (int j = 0; j < m - 1; j++) {
int idx = upper_bound(sg[j].vals.begin(), sg[j].vals.end(), y)
- sg[j].vals.begin();
ll next = sg[j].get(1, 0, sg[j].sz, idx);
if (next >= 0) y = next;
else y = y + (ll)x * (s[j + 1] - s[j]);
//cout << y << "\n";
}
return y;
}
