#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, pll> ans[1001];
void debugmp(int ptr) {
cerr << "Outputting map " << ptr << endl;
for (pair<ll, pll> cur : ans[ptr]) {
cerr << "[" << cur.ff << ", " << cur.ss.ff << "] -> " << cur.ss.ss << endl;
}
cerr << "End of map " << ptr << endl << endl;
}
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]});
}
map<ll, pll> tmp;
auto discretise = [&](int ptr) {
tmp.clear();
ll prev = -1e18; pll range = {-1, -1};
for (map<ll, pll>::iterator it = ans[ptr].begin(); it != ans[ptr].end(); ++it) {
if (it->ss.ss == prev && range.ss + 1 >= it->ff) {
tmp[range.ff].ff = max(tmp[range.ff].ff, it->ss.ff);
range.ss = tmp[range.ff].ff;
continue;
}
if (range.ff != -1) {
tmp[range.ff].ff = min(tmp[range.ff].ff, it->ff - 1);
}
tmp[it->ff] = it->ss;
range = {it->ff, it->ss.ff};
prev = it->ss.ss;
}
ans[ptr].clear();
ans[ptr] = tmp;
};
map<ll, ll> mp;
for (int i = 1; i < m; i++) {
ans[i].clear();
sort(blocks.begin(), blocks.end(), [&](const pll &lhs, const pll &rhs) {
if (lhs.ff != rhs.ff) return lhs.ff < rhs.ff;
return lhs.ss > rhs.ss;
});
mp.clear();
ll dt = s[i] - s[i - 1];
for (int j = 0; j < (int)(blocks.size()); j++) {
ll t = blocks[j].ff, w = blocks[j].ss;
map<ll, ll>::iterator it = mp.upper_bound(t);
if (it != mp.begin()) {
--it;
if (it->ss >= t + w * dt) {
if (it->ff < t) t = it->ss;
else t += w * dt;
blocks[j].ff = t;
continue;
}
}
mp[t] = t + w * dt;
t += w * dt;
blocks[j].ff = t;
}
// for (auto &[t, w] : blocks) cerr << t << ' ' << w << endl;
for (map<ll, ll>::iterator it = mp.begin(); it != mp.end(); ++it) {
// cerr << it->ff << ' ' << it->ss << endl;
ll st = it->ff + 1, en = it->ss - speed * dt;
map<ll, ll>::iterator it2 = it; ++it2;
if (it2 != mp.end()) en = min(en, it2->ff);
if (st <= en) ans[i][st] = {en, it->ss};
}
discretise(i);
// debugmp(i);
}
auto merge = [&](int l, int r) {
int mid = (l + r) >> 1;
int pl = l, pr = mid + 1;
// cerr << l << ' ' << r << ' ' << pl << ' ' << pr << endl;
// debugmp(pl); debugmp(pr);
for (map<ll, pll>::iterator it = ans[pl].begin(); it != ans[pl].end(); ++it) {
ll nx = it->ss.ss + speed * (s[r] - s[mid]);
map<ll, pll>::iterator it2 = ans[pr].upper_bound(it->ss.ss);
if (it2 != ans[pr].begin()) {
--it2;
if (it2->ff <= it->ss.ss && it->ss.ss <= it2->ss.ff) {
nx = it2->ss.ss;
}
}
it->ss.ss = nx;
}
discretise(pl);
// cerr << "RESULT 1:" << endl; debugmp(pl);
for (map<ll, pll>::iterator it = ans[pr].begin(); it != ans[pr].end(); ++it) {
ll tl = it->ff, tr = it->ss.ff;
tl -= speed * (s[mid] - s[l - 1]);
tr -= speed * (s[mid] - s[l - 1]);
// cerr << tl << ' ' << tr << ' ' << it->ss.ss << endl;
bool checked = false;
while (true) {
map<ll, pll>::iterator it2 = ans[pl].lower_bound(tl);
if (!checked) {
checked = true;
if (it2 == ans[pl].begin()) continue;
--it2;
if (it2->ss.ss > it->ss.ss) {
tl = 0; tr = -1; break;
}
if (it2->ss.ff + 1 < tl) continue;
}
if (it2 == ans[pl].end()) break;
// cerr << it2->ff << ' ' << it2->ss.ff << ' ' << it2->ss.ss << endl;
if (it2->ff > tr + 1) break;
// have intersection
// cerr << "CHECKING:\n";
// cerr << tl << ' ' << tr << ' ' << it->ss.ss << endl;
// cerr << it2->ff << ' ' << it2->ss.ff << ' ' << it2->ss.ss << endl;
if (it2->ss.ss <= it->ss.ss) {
if (it2->ss.ss < it->ss.ss) {
if (it2->ss.ff >= tl) exit(1);
it2->ss.ff = min(it2->ss.ff, tl - 1);
} else {
tl = min(tl, it2->ff);
tr = max(tr, it2->ss.ff);
ans[pl].erase(it2);
}
} else {
tr = min(tr, it2->ff - 1);
break;
}
}
// cerr << tl << ' ' << tr << endl;
if (tl <= tr) {
ans[pl][tl] = {tr, it->ss.ss};
}
}
discretise(pl);
// cerr << "RESULT 2:" << endl; debugmp(pl);
};
auto recur = [&](auto&& self, int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
self(self, l, mid); self(self, mid + 1, r);
merge(l, r);
};
recur(recur, 1, m - 1);
// cerr << "FINAL:" << endl; debugmp(1);
// cerr << "END OF FINAL" << endl;
return;
}
long long arrival_time(long long x) {
map<ll, pll>::iterator it = ans[1].upper_bound(x);
if (it != ans[1].begin()) {
--it;
if (it->ff <= x && x <= it->ss.ff) return it->ss.ss;
}
return x + L * speed;
}
