#include "overtaking.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const bool DEBUG = 0;
struct bus {
int num;
ll speed;
ll time;
bool operator<(const bus& other) const {
if (time == other.time) return speed < other.speed;
return time < other.time;
}
void print() {
printf("Num: %d, speed %lld, time %lld\n", num, speed, time);
}
};
struct ST {
ll n;
vector<ll> seg;
ST (int N) : n(N), seg(2*N) {}
void update(ll pos, ll val) {
pos += n;
while (pos > 0) {
seg[pos] = max(seg[pos], val);
pos >>= 1;
}
}
ll query(ll time) {
ll l = n;
time += n;
ll ret = 0;
while (l < time) {
if (l&1) ret = max(ret, seg[l++]);
if (time&1) ret = max(ret, seg[--time]);
time >>= 1;
l >>= 1;
}
return ret;
}
};
struct station {
int num;
ll dist;
vector<bus> buses;
void get_buses(station& other) {
buses.clear();
ll distDiff = dist-other.dist;
sort(other.buses.begin(), other.buses.end());
ll currentMax = 0;
for (bus b : other.buses) {
buses.push_back(b);
currentMax = max(currentMax, b.time + (b.speed*distDiff));
buses.back().time = currentMax;
}
if (DEBUG) {
debug();
}
}
void debug() {
cout << "--------------\n";
cout << num << ", dist: " << dist << "\n";
for (bus b : buses) {
b.print();
}
cout << "--------------\n";
}
};
vector<bus> busesGlobal;
vector<station> stationGlobal;
bus specialBus;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
specialBus.speed = X;
specialBus.num = N;
for (int i = 0; i < N; i++) {
bus b;
b.num = i;
b.speed = W[i];
b.time = T[i];
busesGlobal.push_back(b);
}
for (int i = 0; i < M; i++) {
station stat;
stat.dist = S[i];
stat.num = i;
stationGlobal.push_back(stat);
}
return;
}
long long arrival_time(long long Y)
{
specialBus.time = Y;
vector<bus> newVec;
newVec.insert(newVec.end(), busesGlobal.begin(), busesGlobal.end());
newVec.push_back(specialBus);
sort(newVec.begin(), newVec.end());
stationGlobal[0].buses = newVec;
for (int i = 1; i < stationGlobal.size(); i++) {
stationGlobal[i].get_buses(stationGlobal[i-1]);
}
for (bus b : stationGlobal.back().buses) {
if (b.num == specialBus.num) return b.time;
}
return -1;
}
