#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long speed;
const long long inf=1e18+10;
vector<vector<long long>> ta;
vector<vector<pair<long long, long long>>> pr;
long long asdf=0;
namespace ST {
static const long long NN=1e6;
static const int LG=60;
int ndcnt=1;
long long RR=inf;
long long T[NN*LG], T2[NN*LG];
long long L[NN*LG], R[NN*LG];
void update1(long long ll, long long rr, long long val, long long l=0, long long r=0, long long v=1) {
if(r<ll or rr<l)return;
if(ll<=l and r<=rr) {
T[v]=max(T[v], val);
T2[v]=max(T2[v], max(T[v], r));
return;
}
long long mid=(l+r)/2;
if(L[v]==0)L[v]=++ndcnt;
if(R[v]==0)R[v]=++ndcnt;
update1(ll, rr, val, l, mid, L[v]);
update1(ll, rr, val, mid+1, r, R[v]);
T2[v]=max(T2[v], max(T2[L[v]], T2[R[v]]));
T2[v]=max(T2[v], r);
}
long long query1(long long x, long long l, long long r, long long v) {
if(v==0)return 0;
long long mid=(l+r)/2;
if(x <= mid) {
return max(T[v], query1(x, l, mid, L[v]));
}
else return max(T[v], query1(x, mid+1, r, R[v]));
}
void update(long long l, long long r, long long val) {
update1(l, r, val, 0, RR, 1);
}
long long query(long long x) {
return max(x, query1(x, 0, RR, 1));
}
long long get(long long x, long long tmpval = 0, long long l=0, long long r=RR, long long v=1){
if(v==0) {
if(tmpval>x)return l;
if(r>x)return x+1;
return -1;
}
tmpval=max(tmpval, T[v]);
long long mid=(l+r)/2;
if(max(mid, max(tmpval, T2[L[v]]))>x)return get(x, tmpval, l, mid, L[v]);
long long ttt=get(x, tmpval, mid+1, r, R[v]);
if(ttt!=-1) {
return ttt;
}
if(max(r, tmpval) > x) {
if(tmpval>x)return l;
return x+1;
}
return -1;
}
};
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
speed=X;
asdf=S.back()*speed;
ta=vector<vector<long long>> (M, vector<long long> (N));
for(int i = 0;i<M;i++) {
for(int j = 0;j<N;j++) {
if(i==0)ta[i][j]=T[j];
else ta[i][j]=ta[i-1][j]+(long long)(S[i]-S[i-1])*W[j];
}
if(i){
vector<pair<pair<long long, long long>, int>> idxx;
for(int j = 0;j<N;j++) {
idxx.push_back({{ta[i-1][j], ta[i][j]}, j});
}
sort(idxx.begin(), idxx.end());
for(int k = 1;k<N;k++) {
ta[i][idxx[k].second]=max(ta[i][idxx[k].second], ta[i][idxx[k-1].second]);
}
}
}
pr.resize(M);
for(int i = 0 ;i<M;i++) {
vector<long long> idx;
for(int j = 0;j<N;j++) {
ta[i][j]-=S[i]*speed;
}
if(i) {
for(int j = 0;j<N;j++) {
long long lo = 0, hi = inf;
long long LL=ST::get(ta[i-1][j]);
// while(lo <= hi) {
// long long mid=(lo+hi)/2;
// if(ST::query(mid) > ta[i-1][j]) {
// hi=mid-1;
// LL=mid;
// }
// else {
// lo=mid+1;
// }
// }
idx.push_back(LL);
}
for(int j = 0;j<N;j++) {
if(idx[j]==-1)continue;
// cerr << idx[j] << " " << ta[i][j] << " ";
ST::update(idx[j], (long long)inf, ta[i][j]);
}
// cerr << endl;
}
}
}
long long arrival_time(long long Y) {
long long ans=ST::query(Y);
return ans+asdf;
}
