#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<ll, ll>> car;
int n;
vector<vector<ll>> arr;
vector<ll> s;
int m;
ll x;
// true->fixed
// false +add
map<ll, pair<bool, ll> > seg;
map<ll, pair<bool, ll> > segtmp;
map<ll, pair<bool, ll> > segtmp2;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
for(int i = 0; i < N; ++i) {
if (X < W[i]) {
car.push_back({T[i], W[i]});
}
}
x = X;
n = car.size();
sort(car.begin(), car.end());
arr.push_back(vector<ll>{});
for (int j = 0; j < n; ++j) {
arr.back().push_back(car[j].first);
// std::cout<<car[j].first<<" ";
}
arr.back().push_back(2'100'000'000'000'000'000);
//std::cout<<std::endl;
m = M;
s.push_back(S[0]);
for (int i = 1; i < M; ++i) {
for(int j = 0; j < n; ++j) {
car[j].first += car[j].second * (S[i] - S[i - 1]);
}
for (int j = 1; j < n; ++j) {
car[j].first = max(car[j].first, car[j - 1].first);
}
sort(car.begin(), car.end());
arr.push_back(vector<ll>{});
for (int j = 0; j < n; ++j) {
arr.back().push_back(car[j].first);
// std::cout<<car[j].first<<" ";
}
arr.back().push_back(2'100'000'000'000'000'000);
//std::cout<<std::endl;
s.push_back(S[i]);
}
seg[1'000'000'000'000'000'000LL] = {false, 0};
for(int i = 1; i < m; ++i) {
segtmp.clear();
int j = -1;
ll b_old = seg.begin()->second.second;
for(auto& [key, value] : seg ) {
if (value.first) {
ll e_old = value.second;
while (arr[i - 1][j + 1] < e_old) {
++j;
}
if (j == -1) {
b_old = e_old + 1;
segtmp[key] = {true, e_old + x * (s[i] - s[i - 1])};
} else {
b_old = e_old + 1;
segtmp[key] = {true, max(e_old + x * (s[i] - s[i - 1]), arr[i][j])};
}
} else {
ll e_old = value.second + key;
assert (b_old <= e_old);
while(arr[i - 1][j + 1] < b_old) {
++j;
}
if (j == -1) {
ll tar_old = min(arr[i - 1][j + 1], e_old);
segtmp[tar_old - value.second] = {false, value.second + x * (s[i] - s[i - 1])};
b_old = tar_old + 1;
if (arr[i - 1][j + 1] >= e_old) continue;
++j;
}
while(arr[i - 1][j] < e_old) {
ll tar_old = min({arr[i - 1][j + 1], e_old, arr[i][j] - x * (s[i] - s[i - 1])});
if (tar_old >= b_old) {
segtmp[tar_old - value.second] = {true, arr[i][j]};
b_old = tar_old + 1;
}
ll next_old = min({arr[i - 1][j + 1], e_old});
if (next_old >= b_old) {
segtmp[next_old - value.second] = {false, value.second + x * (s[i] - s[i - 1])};
b_old = next_old + 1;
}
if (arr[i - 1][j + 1] >= e_old) break;
++j;
}
}
}
swap(seg, segtmp);
// for(auto& [key, value] : seg) {
// cout<<key<<" "<<value.first<<" "<<value.second<<std::endl;
// }
// cout<<std::endl;
}
return;
}
long long arrival_time(long long Y)
{
auto it = seg.lower_bound(Y);
return it->second.first ? it->second.second : it->second.second + Y;
}
