#include "overtaking.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 3e5 + 10;
long long l, n, m, x, y;
vector < long long > t;
vector < int > w, s;
struct bus
{
long long t, s, i;
bus(){};
bus(long long _t, long long _s, long long _i)
{
t = _t;
s = _s;
i = _i;
}
};
bus a[maxn];
bool cmp(bus b1, bus b2)
{
if(b1.t != b2.t)return (b1.t < b2.t);
return (b1.s < b2.s);
}
vector < bus > b[maxn];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
l = L;
n = N;
t = T;
x = X;
w = W;
m = M;
s = S;
vector < bus > g;
for (int i = 0; i < n; ++ i)
{
g.pb(bus(t[i], w[i], i));
}
b[0] = g;
sort(b[0].begin(), b[0].end(), cmp);
long long pre = s[0];
for (int i = 1; i < m; ++ i)
{
sort(g.begin(), g.end(), cmp);
long long dist = (s[i] - pre);
long long worst = 0;
vector < bus > v;
for (auto &[t1, s1, nomer]: g)
{
long long arrived = dist * s1 + t1;
worst = max(worst, arrived);
v.pb(bus(worst, s1, nomer));
}
g.clear();
for (auto &[t1, s1, nomer]: v)
g.pb(bus(t1, s1, nomer));
b[i] = g;
sort(b[i].begin(), b[i].end(), cmp);
pre = s[i];
}
return;
}
long long arrival_time(long long Y)
{
y = Y;
long long arrive = y;
long long pre = s[0];
long long cut = n-1;
for (int i = 1; i < m; ++ i)
{
/// cuta e koi sa stignali i-1 po bavno
/// poslednoto po-byrzo
long long lt = 0, rt = n-1, mid, ans = -1;
while(lt <= rt)
{
mid = (lt + rt)/2;
if(b[i-1][mid].t < arrive)
{
ans = mid;
lt = mid + 1;
}
else rt = mid - 1;
}
cut = ans;
// cout << cut << endl;
long long dist = (s[i] - pre);
long long worst = 0;
if(cut != -1)worst = b[i][cut].t;
long long exp_arrive = arrive + dist * x;
arrive = max(exp_arrive, worst);
pre = s[i];
}
return arrive;
}
/**
6 4 10 4 2
20 10 40 0
5 20 20 30
0 1 3 6
*/
