#include "overtaking.h"
#include <set>
#include <map>
#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;
ll distDiff;
vector<bus> buses;
vector<pair<ll, ll>> maxes;
vector<pair<bool, ll>> maxIsBest;
ll addToMap;
void get_buses(station& other) {
// buses.clear();
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;
maxes.emplace_back(b.time, currentMax);
maxIsBest.emplace_back(0,0);
}
if (DEBUG) {
debug();
}
}
pair<ll, bool> get_arrival_time(bus& b) {
addToMap = -1;
if (maxes.empty()) {
return {(b.speed*distDiff) + b.time, 0};
}
auto p = lower_bound(maxes.begin(), maxes.end(), make_pair(b.time, static_cast<ll>(0)));
int place = distance(maxes.begin(), p);
if (b.time > maxes.back().first) {
if (maxes.back().second >= (b.speed*distDiff)+b.time) {
addToMap = place;
}
return {max((b.speed*distDiff) + b.time, maxes.back().second), 0};
}
if (place == 0) {
return {(distDiff*b.speed) + b.time, 0};
}
place--;
if (maxIsBest[place].first) {
return {maxIsBest[place].second, 1};
}
if (maxes[place].second >= (distDiff*b.speed)+b.time) {
addToMap = place;
}
return {max((distDiff*b.speed)+b.time, maxes[place].second), 0};
}
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];
if (b.speed <= X) continue;
// bus specialbus;
// specialbus.speed = X;
// specialbus.time = T[i];
// specialbus.num = N;
busesGlobal.push_back(b);
// busesGlobal.push_back(specialbus);
}
for (int i = 0; i < M; i++) {
station stat;
stat.dist = S[i];
stat.num = i;
stationGlobal.push_back(stat);
}
sort(busesGlobal.begin(), busesGlobal.end());
stationGlobal[0].buses = busesGlobal;
for (int i = 1; i < M; i++) {
stationGlobal[i].get_buses(stationGlobal[i-1]);
}
return;
}
long long arrival_time(long long Y)
{
specialBus.time = Y;
vector<station> a;
bool b;
for (int i = 1; i < stationGlobal.size(); i++) {
pair<ll, bool> p = stationGlobal[i].get_arrival_time(specialBus);
specialBus.time = p.first;
b = p.second;
if (b) {
break;
}
if (stationGlobal[i].addToMap != -1) {
a.push_back(stationGlobal[i]);
}
}
// for (station b : a) {
// b.maxIsBest[b.addToMap] = {specialBus.time, 1};
// }
return specialBus.time;
// 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;
}
