#include "overtaking.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <cstdio>
using namespace std;
#define ll long long
ll arrtime[1005][1005];
set<pair<ll, ll> > intvs[1005];
vector<pair<ll, ll> > buses;
int l, n, x, m;
vector<int> s;
void addintv(int span, ll l, ll r)
{
intvs[span].insert(make_pair(-l, -r));
}
ll find_max_right(int span, ll entertime)
{
auto iter = intvs[span].lower_bound(make_pair(-entertime + 1, -9000000000000000000LL));
if (iter == intvs[span].end() || -iter->second < entertime) {
return entertime;
}
return -iter->second;
}
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;
x = X;
m = M;
s = S;
for (int i = 0; i < N; i++) {
buses.push_back(make_pair(W[i], T[i]));
}
sort(buses.begin(), buses.end());
reverse(buses.begin(), buses.end());
for (int i = 0; i < N; i++) {
ll ctime = buses[i].second;
ll ispeed = buses[i].first;
//printf("Bus departing at %lld, %lld secs/km:\n", ctime, ispeed);
for (int j = 0; j < M - 1; j++) {
ll ntime = max(find_max_right(j, ctime), ctime + ispeed * (ll)(S[j+1]-S[j]));
addintv(j, ctime, ntime);
ctime = ntime;
//printf("Span %d done at time %lld\n", j, ctime);
}
}
}
long long arrival_time(long long Y)
{
ll ctime = Y;
for (int j = 0; j < m - 1; j++) {
ctime = max(find_max_right(j, ctime), ctime + x * (ll)(s[j+1]-s[j]));
}
return ctime;
}
