#include "overtaking.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
#define asst(x) if(!(x)) exit(2)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
struct bus {
ll t; int w;
};
struct ivl {
ll l, r, ans;
};
vvll t, e, me;
vi pos;
int X;
vector<vector<ivl>> stored;
struct segTree {
struct node {
ll val;
bool lz;
};
vector<node> seg;
vi& vls;
int cl, cr;
segTree(vi& vals) : vls(vals), cl(0), cr((int) vals.size() - 1) {
seg.resize(4 * vals.size(), {-1, false});
}
void push(int v, int l, int r) {
if(l < r) {
if(seg[v].lz) {
seg[2*v].val = seg[v].val, seg[2*v+1].val = seg[v].val;
seg[2*v].lz = seg[2*v+1].lz = true;
seg[v].lz = false;
seg[v].val = -1;
}
}
}
void upd(int v, int nl, int nr, int l, int r, ll to) {
push(v, nl, nr);
if(l > r) return;
if(nl == l && nr == r) {
seg[v].val = to;
seg[v].lz = true;
} else {
int mid = (nl+nr)/2;
upd(2*v, nl, mid, l, min(r, mid), to);
upd(2*v+1, mid+1, nr, max(mid+1, l), r, to);
}
}
ll qu(int v, int nl, int nr, int i) {
if(nl == i && nr == i) return seg[v].val;
int mid = (nl+nr)/2;
if(i <= mid) return qu(2*v, nl, mid, i);
else return qu(2*v+1, mid+1, nr, i);
}
int binSearch(ll val) {
auto nex = lower_bound(all(this->vls), val);
asst(nex != this->vls.end() && *nex == val);
return nex - vls.begin();
}
void upd(ll l, ll r, ll to) {
upd(1, cl, cr, binSearch(l), binSearch(r), to);
}
ll qu(ll i) {
return qu(1, cl, cr, binSearch(i));
}
};
segTree* seg = nullptr;
void sortByTime(vector<bus>& bs) {
sort(all(bs), [](bus a, bus b){return a.t < b.t;});
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
vll nt; vi nw;
set<int> rem;
forR(i, N) if(W[i] <= X) rem.insert(i);
forR(i, N) if(!rem.count(i)) {
nt.push_back(T[i]);
nw.push_back(W[i]);
}
N -= rem.size();
T = nt, W = nw;
t = vvll(M, vll(N)), e = vvll(M-1, vll(N)), me = vvll(M-1, vll(N));
pos = S;
vector<bus> bs;
forR(i, N) {
bs.push_back({T[i], W[i]});
}
forR(i, M-1) {
sortByTime(bs);
forR(j, N) t[i][j] = bs[j].t;
forR(j, N) e[i][j] = bs[j].t + (ll) bs[j].w * (S[i+1] - S[i]);
ll cm = 0;
for(int j = 0; j < N; ){
ll cur = bs[j].t;
int k=j;
for(; k < N && bs[k].t == cur; ++k) {}
REP(l, j, k) bs[l].t = max(e[i][l], cm);
REP(l, j, k) cm = max(cm, e[i][l]);
j = k;
}
}
forR(j, N) t[M-1][j] = bs[j].t;
::X = X;
forR(i, M-1) {
if(N > 0) me[i][0] = e[i][0];
REP(j, 1, N) me[i][j] = max(e[i][j], me[i][j-1]);
}
stored = vector<vector<ivl>>(M-1);
for(int i = M-2; i >= 0; --i) {
ll toNex = (ll) X * (S[i+1]-S[i]), toHere = (ll) X * (S[i] - S[0]);
forR(j, N) {
ll lo = t[i][j]+1;
ll hi = j == N-1 ? me[i][j] - toNex : min(me[i][j] - toNex, t[i][j+1]);
ll nlo = lo - toHere, nhi = hi - toHere;
ll find = me[i][j] - toNex - toHere;
bool found = false;
for(int k = i+1; !found && k < M-1; ++k) {
for(auto [l, r, cAns] : stored[k]) {
if(l <= find && r >= find) {
asst(!found);
found = true;
stored[i].push_back({nlo, nhi, cAns});
}
}
}
if(!found) stored[i].push_back({nlo, nhi, me[i][j] + (ll) X * (S[M-1] - S[i+1])});
}
}
}
long long arrival_time(long long Y)
{
int M = (int) pos.size(), N = t[0].size();
forR(i, M-1) {
for(auto [l, r, ans] : stored[i]) {
if(l <= Y && r >= Y) return ans;
}
}
return Y + (ll) X * (pos[M-1] - pos[0]);
}
