#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma GCC optimize("O3")
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;
struct IST_node {
long long l, r;
long long mx = 0;
IST_node *left = nullptr, *right=nullptr;
IST_node(long long _l, long long _r) {
l = _l;
r = _r;
}
void extend() {
if(!left and l<r) {
long long mid = (l+r)>>1;
left = new IST_node(l, mid);
right = new IST_node(mid+1, r);
}
}
long long query(long long x) {
if(l==r)return mx;
long long m=(l+r)/2;
if(x<=m) {
if(left==nullptr)return mx;
return max(mx, left->query(x));
}
else {
if(right==nullptr)return mx;
return max(mx, right->query(x));
}
}
void modify(long long L, long long R, long long val) {
if(l > r)return;
if(R < l or L > r)return;
if(L <= l and r <= R) {
mx=max(mx, val);
return;
}
extend();
right->modify(L, R, val);
left->modify(L, R, val);
}
};
class IST {
private:
IST_node *root;
public:
IST(long long n) {
root = new IST_node(0,n);
}
long long query(long long x) {
return max(x, root->query(x));
}
void modify(long long l, long long r, long long val) {
root->modify(l, r, val);
}
};
IST st((long long)inf+10);
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=inf;
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++) {
st.modify(idx[j], (long long)1e18+5, ta[i][j]);
}
}
}
}
long long arrival_time(long long Y) {
long long ans=st.query(Y);
return ans+asdf;
}
