#include "overtaking.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
const ll INF = 2e18+5;
ll sh;
set <piii> seg;
void init(int L,int N,vector<ll>T,vector<int>W,int X,int M,vector<int>S) {
sh = (ll)X*L;
vector <pii> V;
for (int i=0;i<N;i++) {
if (W[i] > X) {
V.push_back({T[i]+sh,W[i]-X});
}
}
N = V.size();
if (!N) {
return;
}
vector <pii> U;
for (int i=1;i<M;i++) {
int s = S[i]-S[i-1];
sort(V.begin(),V.end());
for (int i=0;i<N;i++) {
V[i].fi += V[i].se*s;
}
for (int i=1;i<N;i++) {
V[i].fi = max(V[i].fi,V[i-1].fi);
}
for (int i=N-1;i>=0;i--) {
U.push_back({V[i].fi-V[i].se*s,V[i].fi});
}
}
reverse(U.begin(),U.end());
seg.insert({0,{0,0}});
seg.insert({INF,{INF,INF}});
for (pii u : U) {
piii X = {u.se,{0,0}};
auto S = lower_bound(seg.begin(),seg.end(),X);
if (u.se < S->se.fi) {
X = {u.se-1,{u.fi+1,u.se}};
}
else if (u.fi+1 >= S->se.fi) {
continue;
}
else {
X = {S->fi,{u.fi+1,S->se.se}};
while (1) {
if (S->fi < X.se.fi) {
break;
}
if (S->se.fi < X.se.fi) {
seg.insert({X.se.fi-1,S->se});
}
piii Y = *S;
S--;
seg.erase(Y);
}
}
seg.insert(X);
}
}
ll arrival_time(ll Y) {
piii X = {Y+sh,{0,0}};
piii S = *lower_bound(seg.begin(),seg.end(),X);
if (S.se.fi <= X.fi) {
return S.se.se;
}
return X.fi;
}
