#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000;
const int MAX_M = 1000;
const long long INF = 1e18;
struct bus {
long long t;
int v;
int p;
};
struct answer {
long long l, r, a, b;
};
int n, m, x;
bus buses[MAX_M][MAX_N + 1];
long long timeByBus[MAX_M][MAX_N + 1];
int stations[MAX_M];
vector<answer> ans;
vector<answer> get_answer_between_stations(int s) {
vector<answer> betweenStations;
betweenStations.push_back({0, buses[s][0].t, 1, (long long)x * (stations[s + 1] - stations[s])});
for (int i = 0; i < n; i++) {
//pleaca intre i si i + 1
//daca pleaca devreme e posibil sa ramana impotmolit
//daca pleaca tarziu poate sa scape de ambuteiaj
//pleaca
long long l = buses[s][i].t + 1, r = buses[s][i + 1].t;
long long p = timeByBus[s + 1][buses[s][i].p] - (long long)x * (stations[s + 1] - stations[s]);
if (l > r)
continue;
// printf("%d %lld %lld %lld\n", i, l, r, p);
if (l < p)
betweenStations.push_back({l, min(p - 1, r), 0, timeByBus[s + 1][buses[s][i].p]});
if (p <= r)
betweenStations.push_back({max(p, l), r, 1, (long long)x * (stations[s + 1] - stations[s])});
}
return betweenStations;
}
vector<answer> get_answers_by_station(int s) {
vector<answer> crtStation;
if (s == m - 1) {
crtStation.push_back({0, INF, 1, 0});
return crtStation;
}
vector<answer> nextStation = get_answers_by_station(s + 1);
vector<answer> betweenStations = get_answer_between_stations(s);
int first = 0, last = -1;
for (answer bet: betweenStations) {
long long l = bet.a * bet.l + bet.b, r = bet.a * bet.r + bet.b;
while (last + 1 < (int)nextStation.size() && r >= nextStation[last + 1].l)
last++;
while (first < (int)nextStation.size() && l > nextStation[last].r)
first++;
for (int i = 0; i < (int)nextStation.size(); i++) {
answer nxt = nextStation[i];
answer crt;
if (nxt.r < l || nxt.l > r)
continue;
crt.a = bet.a * nxt.a;
crt.b = nxt.a * bet.b + nxt.b;
if (bet.a == 0) {
crt.l = bet.l;
crt.r = bet.r;
} else {
crt.l = (max(l, nxt.l) - bet.b) / bet.a;
crt.r = (min(r, nxt.r) - bet.b) / bet.a;
}
if (crt.l > crt.r)
continue;
// printf("a (%lld %d) %lld %lld\n", bet.l, i, crt.l, crt.r);
crtStation.push_back(crt);
}
}
// printf("STATIA %d\n", s);
// printf("BETWEEN\n");
// for (answer bet: betweenStations)
// printf("[%lld %lld] %lld %lld\n", bet.l, bet.r, bet.a, bet.b);
// printf("CURENT\n");
// for (answer crt: crtStation)
// printf("[%lld %lld] %lld %lld\n", crt.l, crt.r, crt.a, crt.b);
// printf("----------------------\n");
return crtStation;
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
n = N;
m = M;
x = X;
for (int i = 0; i < n; i++)
buses[0][i] = {T[i], W[i], i};
for (int i = 0; i < m; i++)
stations[i] = S[i];
for (int j = 0; j < m - 1; j++) {
sort(buses[j], buses[j] + n, [](bus a, bus b) {
if (a.t == b.t)
return a.v < b.v;
return a.t < b.t;
} );
for (int i = 0; i < n; i++)
buses[j + 1][i] = buses[j][i];
for (int i = 0; i < n; i++)
buses[j + 1][i].t = buses[j][i].t + (long long)buses[j][i].v * (stations[j + 1] - stations[j]);
for (int i = 1; i < n; i++)
buses[j + 1][i].t = max(buses[j + 1][i].t, buses[j + 1][i - 1].t);
// for (int i = 0; i < n; i++)
// printf("%lld ", buses[j + 1][i].t);
// printf("\n");
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++)
timeByBus[j][buses[j][i].p] = buses[j][i].t;
buses[j][n].t = INF;
}
ans = get_answers_by_station(0);
}
long long arrival_time(long long y) {
int l = 0, r = ans.size();
while (r - l > 1) {
int mid = (l + r) / 2;
if (ans[mid].l > y)
r = mid;
else
l = mid;
}
return ans[l].a * y + ans[l].b;
}
