#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll base;
vector<vector<ll>> arrival;
vector<pair<ll, ll>> interval;
vector<pair<ll, ll>> segment_tree;
ll segsz;
ll segd;
void propagate(ll node) {
ll set = segment_tree[node].second;
if(set == -1) return;
segment_tree[node].second = -1;
segment_tree[node].first = max(segment_tree[node].first, set);
if(node >= segsz) {
return;
}
else {
segment_tree[2 * node].second = max(segment_tree[2 * node].second, set);
segment_tree[2 * node + 1].second = max(segment_tree[2 * node + 1].second, set);
}
}
void set_interval(ll a, ll b, ll val) {
// interval (a, b]
auto l = lower_bound(interval.begin(), interval.end(), make_pair(a, -1ll));
assert(l->first == a);
auto r = lower_bound(interval.begin(), interval.end(), make_pair(b, -1ll));
assert(r->first == b);
l++;
a = l->second;
b = r->second;
ll lptr = 1;
ll rptr = 1;
for(int i = segd; i > 0; i--) {
propagate(lptr);
propagate(2 * lptr);
propagate(2 * lptr + 1);
propagate(rptr);
propagate(2 * rptr);
propagate(2 * rptr + 1);
bool add = lptr != rptr;
if((1 << (i - 1)) & a) {
lptr = 2 * lptr + 1;
}
else {
if(add) segment_tree[2 * lptr + 1].second = val;
lptr = 2 * lptr;
}
if((1 << (i - 1)) & b) {
if(add) segment_tree[2 * rptr].second = val;
rptr = 2 * rptr + 1;
}
else {
rptr = 2 * rptr;
}
}
propagate(lptr);
propagate(rptr);
while(lptr != 0) {
propagate(lptr >> 1);
propagate(rptr >> 1);
segment_tree[lptr].first = val;
segment_tree[rptr].first = val;
lptr >>= 1;
rptr >>= 1;
}
}
ll get_interval(ll a) {
a = lower_bound(interval.begin(), interval.end(), make_pair(a, -1ll))->second;
ll lptr = 1;
for(int i = segd; i > 0; i--) {
propagate(lptr);
propagate(2 * lptr);
propagate(2 * lptr + 1);
if((1 << (i - 1)) & a) {
lptr = 2 * lptr + 1;
}
else {
lptr = 2 * lptr;
}
}
return segment_tree[lptr].first;
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
base = 1ll * X * L;
for(int i = 0; i < N; i++) {
W[i] -= X;
}
for(int i = 0; i < N; i++) {
if(W[i] <= 0) {
W[i] = W.back();
T[i] = T.back();
W.pop_back();
T.pop_back();
N--;
i--;
}
}
arrival.resize(M, vector<ll>(N));
arrival[0] = T;
for(int i = 1; i < M; i++) {
vector<tuple<ll, int, ll, int>> expected(N); // departure, speed, arrival, node
int distance = S[i] - S[i - 1];
for(int j = 0; j < N; j++) {
expected[j] = make_tuple(arrival[i - 1][j], W[j], arrival[i - 1][j] + 1ll * W[j] * distance, j);
}
sort(expected.begin(), expected.end());
for(int j = 1; j < N; j++) {
tuple<ll, int, ll, int> t = expected[j];
expected[j] = make_tuple(get<0>(t), get<1>(t), max(get<2>(t), get<2>(expected[j - 1])), get<3>(t));
}
for(int j = 0; j < N; j++) {
arrival[i][get<3>(expected[j])] = get<2>(expected[j]);
}
}
vector<ll> used;
for(vector<ll> vec : arrival) {
for(ll a : vec) used.push_back(a);
}
used.push_back(0);
used.push_back(INF);
sort(used.begin(), used.end());
for(ll i = 0, ix = 0; i < N * M + 2; i++) {
if(i == 0 || used[i] != used[i - 1]) {
interval.push_back(make_pair(used[i], ix++));
}
}
segsz = 1;
segd = 0;
while(segsz < interval.size()) {
segsz <<= 1;
segd++;
}
segment_tree.resize(segsz * 2, make_pair(-1, -1));
for(int i = M - 2; i >= 0; i--) {
vector<ll> vec(N);
for(int j = 0; j < N; j++) {
ll x = get_interval(arrival[i + 1][j]);
if(x == -1) x = arrival[i + 1][j];
vec[j] = x;
}
for(int j = 0; j < N; j++) {
set_interval(arrival[i][j], arrival[i + 1][j], vec[j]);
}
}
}
long long arrival_time(long long Y) {
ll ret = get_interval(Y);
if(ret == -1) ret = Y;
return ret + base;
}
