#include "overtaking.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define int long long
using namespace std;
int n, m, x;
vector<int> t, w;
vector<signed> s;
vector<vector<int>> dp;
vector<vector<pair<int, int>>> ttime;
vector<int> base;
void init(signed L, signed N, vector<int> T, vector<signed> W, signed X, signed M, vector<signed> S) {
n=N, m=M, x=X, s=S;
for (int i=0; i<n; i++) {
if (W[i]>X) t.pb(T[i]), w.pb(W[i]);
}
n=sz(t);
dp.resize(n, vector<int>(m, 1e18));
ttime.resize(n, vector<pair<int, int>>(m));
vector<vector<int>> time2(n, vector<int>(m));
vector<vector<int>> empl(n, vector<int>(m));
{
vector<pair<pair<int, int>, int>> bus;
for (int i=0; i<n; i++) bus.pb({{t[i], w[i]}, i});
sort(all(bus));
for (int i=0; i<n; i++) {
base.pb(bus[i].fi.fi);
ttime[i][0]={bus[i].fi.fi, bus[i].se};
}
}
for (int act=1; act<m; act++) {
vector<pair<pair<int, int>, int>> bus;
for (int i=0; i<n; i++) bus.pb({{ttime[i][act-1].fi, w[ttime[i][act-1].se]}, ttime[i][act-1].se});
sort(all(bus));
int sz=s[act]-s[act-1];
int latest=0;
for (int i=0; i<n; i++) {
int nb=bus[i].fi.fi+sz*bus[i].fi.se;
cmax(latest, nb);
ttime[i][act]={latest, bus[i].se};
time2[bus[i].se][act]=latest;
empl[bus[i].se][act]=i;
}
}
for (int i=0; i<n; i++) dp[i][m-1]=ttime[i][m-1].fi;
for (int act=m-2; act>=0; act--) {
int nxt=-1;
for (int i=0; i<n; i++) {
if (i && ttime[i-1][act].fi!=ttime[i][act].fi) nxt=ttime[i-1][act].se;
else if (i && nxt!=-1 && w[ttime[i-1][act].se]>w[nxt]) nxt=ttime[i-1][act].se;
if (nxt==-1) {
dp[i][act]=ttime[i][act].fi+x*(L-s[act]);
continue;
}
// int nxt=ttime[i-1][act].se;
int l=act+1, r=m-1, ans=-1;
while (l<=r) {
int mid=(l+r)/2;
int posact=ttime[i][act].fi+x*(s[mid]-s[act]);
int posnxt=ttime[i-1][mid].fi;
if (posnxt>=posact) {
ans=mid;
r=mid-1;
} else {
l=mid+1;
}
}
// if (i==2 && act==1) cout << nxt << ' ' << ans << endl;
if (ans==-1) {
dp[i][act]=ttime[i][act].fi+x*(L-s[act]);
} else {
dp[i][act]=dp[i-1][ans];
}
}
}
// for (int i=0; i<n; i++) {
// for (int j=0; j<m; j++) {
// cout << ttime[i][j].fi << ',' << dp[i][j] << ' ';
// }
// cout << endl;
// }
}
int arrival_time(int y) {
if (!n || base[0]>=y) return y+x*s.back();
int before=lower_bound(all(base), y)-base.begin()-1;
int l=0, r=m-1, ans=0;
while (l<=r) {
int mid=(l+r)/2;
int pos=y+x*s[mid];
if (ttime[before][mid].fi>=pos) {
r=mid-1;
ans=mid;
} else {
l=mid+1;
}
}
// cout << "ans: " << ans << ' ' << before << endl;
return dp[before][ans];
}
/*
180 130 180 55
0: 30 0
0 0: 60
0 1: 80
0 2: 130
0 3: 180
1: 20 10
1 0: 80
1 1: 80
1 2: 100
1 3: 130
2: 20 40
2 0: 100
2 1: 130
2 2: 180
2 3: 180
3: 5 20
3 0: 80
3 1: 80
3 2: 70
3 3: 55
0
50
*/
