#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
long long t[1003][1003],e[1003][1003];
long long ord[1003],cj;
bool cmp (int a, int b)
{
if(t[a][cj-1] < t[b][cj-1])
return true;
if(t[a][cj-1] > t[b][cj-1])
return false;
return e[a][cj] < e[b][cj];
}
struct ura
{
long long l,r,x;
};
vector<ura>vc;
bool cmp2 (ura a, ura b)
{
if(a.x == b.x)
{
return a.r < b.r;
}
return a.x>b.x;
}
vector<long long>coords;
vector<long long>norms;
unordered_map<long long,int>invnorm;
long long aint[16000005];
long long realcoords[4000005];
void upd (int nod, int l, int r, int ul, int ur, long long val)
{
if(ul<=l && r <= ur)
{
aint[nod] = max(aint[nod],val);
return;
}
if(ur < l || r < ul)
return;
int mid = ((l+r)>>1);
upd(nod<<1,l,mid,ul,ur,val);
upd((nod<<1)|1,mid+1,r,ul,ur,val);
}
long long qry (int nod, int l, int r, int pz)
{
if(pz < l || r < pz)
return 0;
if(l == r)
return aint[nod];
int mid = ((l+r)>>1);
long long a = max(qry(nod<<1,l,mid,pz), qry((nod<<1)|1,mid+1,r,pz));
return max(a, aint[nod]);
}
void build (int nod, int l, int r)
{
if(l == r)
{
aint[nod] = realcoords[l];
return;
}
int mid = ((l+r)>>1);
build(nod<<1,l,mid);
build((nod<<1)|1,mid+1,r);
}
long long xx,kk,ll;
long long idkk,okt;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
ll = L;
xx = X;
int i,j;
for(i=0;i<N;++i)
t[i][0] = T[i];
for(i=0;i<N;++i)
ord[i]=i;
for(j = 1; j < M; ++j)
{
for(i = 0 ; i < N; ++i)
{
e[i][j] = t[i][j-1] + W[i] * 1LL * (S[j] - S[j-1]);
// cout<<i<<' '<<t[i][j-1]<<' '<<W[i]<<' '<<S[j]<<' '<<S[j-1]<<' '<<e[i][j]<<'\n';
}
cj = j;
sort(ord,ord+N,cmp);
long long mxc = 0;
for(i = 0; i < N; ++i)
{
int vlc = ord[i];
// cout<<vlc<<' ';
mxc = max(mxc, e[vlc][j]);
t[vlc][j] = mxc;
}
}
for(i = 0; i < N; ++i)
{
for(j = 1; j < M; ++j)
{
ura x;
x.l = t[i][j-1] - S[j-1]*1LL*X + 1;
x.r = t[i][j] - S[j]*1LL*X;
x.x = j;
if(x.l > x.r)
continue;
vc.push_back(x);
coords.push_back(x.l);
coords.push_back(x.r);
}
// cout<<'\n';
}
if(coords.empty())
{
okt = 1;
return;
}
sort(coords.begin(),coords.end());
long long k = 1;
norms.push_back(1);
invnorm[coords[0]] = 1;
realcoords[1] = coords[0];
for(int i = 1; i < coords.size(); ++i)
{
if(coords[i] != coords[i-1])
k+=2;
// cout<<"coord: "<<coords[i]<<'\n';
invnorm[coords[i]] = k;
realcoords[k] = coords[i];
norms.push_back(k);
}
// cout<<"\n\n";
build(1,1,k);
sort(vc.begin(),vc.end(),cmp2);
for(int i = 0; i < vc.size();++i)
{
ura x = vc[i];
int l = invnorm[x.l];
int r = invnorm[x.r];
long long val = qry(1,1,k,r);
// cout<<"upd "<<x.x<<' '<<l<<' '<<r<<' '<<val<<'\n';
upd(1,1,k,l,r,val);
}
kk = k;
}
long long arrival_time(long long Y)
{
if(okt)
{
return Y + ll * 1LL * xx;
}
int pas = (1<<21);
int pz = -1;
while(pas)
{
if(pz+pas < (int)coords.size() && coords[pz+pas]<=Y)
pz += pas;
pas>>=1;
}
if(pz == -1)
{
return Y + ll * 1LL * xx;
}
if(pz == (int)coords.size()-1 && Y >= coords[pz])
return Y + ll * 1LL * xx;
//cout<<"here "<<pz<<'\n';
if(coords[pz] == Y)
{
//cout<<invnorm[3]<<"<-\n";
//cout<<"idk "<<qry(1,1,kk,invnorm[coords[pz]])<<'\n';
return max(Y,qry(1,1,kk,invnorm[coords[pz]])) + ll * 1LL * xx;
}
else
{
return max(Y,qry(1,1,kk,invnorm[coords[pz]] + 1)) + ll * 1LL * xx;
}
}
/*
3 1 3 2 7
2
4
0 3
1 2 3 4 5 6 7
*/
