#include "overtaking.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 1000 + 10;
const int MAXQ = 5000 + 10;
const int BUCKET_SIZE = 32;
llong x;
int n, m, l;
struct SegmentTree
{
llong tree[4 * MAXN];
void build(int l, int r, int node)
{
if (l == r)
{
tree[node] = 1e18;
return;
}
int mid = l + r >> 1;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node] = std::min(tree[2*node], tree[2*node + 1]);
}
void update(int l, int r, int node, int queryPos, llong queryVal)
{
if (l == r)
{
tree[node] = std::min(tree[node], queryVal);
return;
}
int mid = l + r >> 1;
if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
tree[node] = std::min(tree[2*node], tree[2*node + 1]);
}
int search(int l, int r, int node, int queryL, int queryR, llong queryVal)
{
if (queryR < l || r < queryL || tree[node] >= queryVal)
{
return -1;
}
if (l == r)
{
return l;
}
int mid = l + r >> 1;
int res = search(l, mid, 2*node, queryL, queryR, queryVal);
if (res != -1) return res;
return search(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
}
void build()
{
build(0, m - 2, 1);
}
void update(int pos, llong val)
{
update(0, m - 2, 1, pos, val);
}
int search(int l, int r, llong val)
{
return search(0, m - 2, 1, l, r, val);
}
};
SegmentTree tree;
std::vector <int> s;
std::vector <std::pair <llong,int>> buses;
std::vector <std::pair <llong,llong>> t[MAXN];
std::vector <std::pair <llong,llong>> continueThrough[MAXN];
std::vector <std::pair <llong,llong>> intervals[BUCKET_SIZE];
std::vector <llong> ifBegining[MAXN];
int findIntersection(int pos, llong time)
{
int l = 0, r = t[pos].size(), mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (t[pos][mid].first < time) l = mid;
else r = mid;
}
return l;
}
long long my_arrival_time(int pos, llong time)
{
for (int i = pos ; i + 1 < m ; ++i)
{
int l = 0, r = t[i].size(), mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (t[i][mid].first < time) l = mid;
else r = mid;
}
time = std::max(time + 1LL * x * (s[i + 1] - s[i]), t[i][l].second);
}
return time;
}
void init(int L, int N, std::vector <long long> T, std::vector <int> W, int X, int M, std::vector <int> S)
{
n = N;
m = M;
s = S;
x = X;
for (int i = 0 ; i < n ; ++i)
{
buses.push_back({T[i], W[i]});
}
for (int i = 0 ; i + 1 < m ; ++i)
{
t[i].push_back({-1, 0});
std::vector <std::pair <llong,int>> newBuses;
std::sort(buses.begin(), buses.end());
for (const auto &[time, w] : buses)
{
llong arrive = 1LL * (s[i + 1] - s[i]) * w + time;
if (arrive > t[i].back().second)
{
t[i].push_back({time, arrive});
}
newBuses.push_back({t[i].back().second, w});
}
buses = newBuses;
}
std::vector <std::pair <int,int>> v;
for (int i = 0 ; i + 1 < m ; ++i)
{
for (int j = 1 ; j < t[i].size() ; ++j)
{
v.push_back({i, j});
}
}
std::sort(v.begin(), v.end(), [&](auto &a, auto &b)
{
return t[a.first][a.second].second - 1LL * s[a.first + 1] * x > t[b.first][b.second].second - 1LL * s[b.first + 1] * x;
});
for (int i = 0 ; i + 1 < m ; ++i)
{
ifBegining[i].resize(t[i].size());
continueThrough[i].push_back({1e18, 0});
}
tree.build();
for (const auto &[i, j] : v)
{
bool done = false;
ifBegining[i][j] = 1LL * (s[m - 1] - s[i + 1]) * x + t[i][j].second;
int u = tree.search(i + 1, m - 1, t[i][j].second - 1LL * s[i + 1] * x);
if (u != -1)
{
int l = 0, r = t[u].size(), mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (!ifBegining[u][mid]) l = mid;
else if (t[i][j].second - 1LL * s[i + 1] * x <= t[u][mid].first - 1LL * s[u] * x) r = mid;
else l = mid;
}
ifBegining[i][j] = ifBegining[u][l];
}
tree.update(i, t[i][j].first - 1LL * s[i] * x);
}
for (int i = 0 ; i + 1 < m ; ++i)
{
for (int j = 1 ; j < t[i].size() ; ++j)
{
if (t[i][j].first - 1LL * x * s[i] + 1 > t[i][j].second - 1LL * x * s[i + 1] - 1)
{
continue;
}
intervals[i / BUCKET_SIZE].push_back({t[i][j].first - 1LL * x * s[i] + 1, t[i][j].second - 1LL * x * s[i + 1] - 1});
}
}
for (int i = 0 ; i < BUCKET_SIZE ; ++i)
{
if (intervals[i].empty())
{
continue;
}
std::vector <std::pair <llong,llong>> curr;
std::sort(intervals[i].begin(), intervals[i].end());
curr.push_back(intervals[i][0]);
for (int j = 1 ; j < intervals[i].size() ; ++j)
{
if (intervals[i][j].first <= curr.back().second)
{
curr.back().second = intervals[i][j].second;
} else
{
curr.push_back(intervals[i][j]);
}
}
intervals[i] = curr;
}
}
long long arrival_time(llong time)
{
int idx = 0;
int bucket = 0;
while (idx < m - 1)
{
int l = -1, r = intervals[bucket].size(), mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (intervals[bucket][mid].first <= time) l = mid;
else r = mid;
}
if (l != -1 && time <= intervals[bucket][l].second)
{
break;
}
idx += BUCKET_SIZE;
bucket++;
}
if (idx >= m - 1)
{
return 1LL * x * s[m - 1];
}
for (int i = idx ; i + 1 < m ; ++i)
{
int l = 0, r = t[i].size(), mid;
while (l < r - 1)
{
mid = l + r >> 1;
if (t[i][mid].first < time) l = mid;
else r = mid;
}
if (l != 0 && time + 1LL * x * (s[i + 1] - s[i]) < t[i][l].second)
{
return ifBegining[i][l];
}
time += 1LL * x * (s[i + 1] - s[i]);
}
return time;
}
