#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
ll L;
ll speed;
map<ll, ll> ans; // (l, r]
void DebugMap() {
cerr << "DEBUG MAP:" << endl;
for (pll cur : ans) {
cerr << cur.ff << ' ' << cur.ss << endl;
}
cerr << "END" << endl << endl;
}
void AddRange(ll l, ll r) {
// cerr << "ADDING " << l << ' ' << r << endl;
map<ll, ll>::iterator it;
// find extension
it = ans.lower_bound(r);
if (it != ans.begin()) {
--it;
r = max(r, it->ss);
}
// check if being contained
it = ans.upper_bound(l);
if (it != ans.begin()) {
--it;
if (it->ff <= l && r <= it->ss) return;
}
// remove all that are contained
while (true) {
it = ans.lower_bound(l);
if (it == ans.end()) break;
if (l <= it->ff && it->ss <= r) {
ans.erase(it);
} else break;
}
ans[l] = r;
// DebugMap();
}
void init(int L_, int n, vector<long long> T, vector<int> W, int X, int m, vector<int> S) {
vector<ll> s(m);
for (int i = 0; i < m; i++) s[i] = S[i];
L = L_; speed = X;
vector<pll> blocks;
for (int i = 0; i < n; i++) {
if (W[i] <= speed) continue;
blocks.pb({T[i], W[i]});
}
n = blocks.size();
ll times[m][n];
for (int i = 0; i < n; i++) times[0][i] = blocks[i].ff;
for (int i = 1; i < m; i++) {
vector<pair<pll, int>> range;
ll dt = s[i] - s[i - 1];
for (int j = 0; j < n; j++) {
range.pb({{times[i - 1][j], times[i - 1][j] + blocks[j].ss * dt}, j});
}
sort(range.begin(), range.end());
ll mx = -1e18;
for (int j = 0; j < n; j++) {
mx = max(mx, range[j].ff.ss);
times[i][range[j].ss] = mx;
}
}
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < n; j++) {
// cerr << times[i][j] << ' ';
// }
// cerr << endl;
// }
// cerr << endl;
for (int i = m - 1; i >= 1; i--) {
vector<pll> range;
for (int j = 0; j < n; j++) {
ll st = times[i - 1][j] - speed * s[i - 1];
ll en = times[i][j] - speed * s[i];
range.pb({st, en});
}
sort(range.begin(), range.end());
for (pll cur : range) {
AddRange(cur.ff, cur.ss);
}
}
}
long long arrival_time(long long x) {
ll res = x + L * speed;
if (ans.empty()) return res;
map<ll, ll>::iterator it = ans.lower_bound(x);
if (it != ans.begin()) {
--it;
res = max(res, it->ss + L * speed);
}
return res;
}
