#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 95;
const ll INF = 1e18;
ll mint[MAXN][MAXN];//mint[i][j] =def= the minimum time to get from i to j, knowing that you start at time 0 in node i
ll invt[MAXN][MAXN];
void get_min(vector<pair<ll,ll>>&x, vector<pair<ll,ll>> y)
{
if(y.empty())
return;
if(x.empty())
{
swap(x, y);
return;
}
vector<pair<ll,ll>> aux;
int poz_x = 0, poz_y = 0;
while(poz_x < x.size() || poz_y < y.size())
{
if(poz_y == y.size() || (poz_x < x.size() && x[poz_x] < y[poz_y]))
{
aux.push_back(x[poz_x]);
poz_x++;
}
else
{
aux.push_back(y[poz_y]);
poz_y++;
}
}
x.clear();
ll mnm = INF;
for(int i=(int)aux.size()-1;i>=0;i--)
{
if(aux[i].second < mnm && (i == 0 || aux[i].first != aux[i-1].first))
{
mnm = aux[i].second;
x.push_back(aux[i]);
}
}
reverse(x.begin(), x.end());
}
vector<pair<ll,ll>> apply_edge(const vector<pair<ll,ll>>&x, ll L, ll C)
{
if(x.empty())
return x;
vector<pair<ll,ll>> rez;
for(auto it:x)
{
if(it.first - L >= 0)
{
if(it.first < C)
{
rez.push_back({it.first - L, it.second + L});
}
else
{
rez.push_back({C - L, it.second + L});
break;
}
}
}
return rez;
}
ll query(vector<pair<ll,ll>>&x, ll t)
{
auto it = lower_bound(x.begin(), x.end(), make_pair(t, -1LL));
if(it == x.end())
return INF;
else
return (*it).second;
}
vector<pair<ll,ll>> combine_chained(vector<pair<ll,ll>> x, vector<pair<ll,ll>> y)
{
if(x.empty() || y.empty()) return {};
vector<pair<ll,ll>> newx, newy;
int poz_y = 0;
for(auto it:x)
{
while(poz_y < y.size() && it.first + it.second > y[poz_y].first)
poz_y++;
if(poz_y == y.size())
break;
newx.push_back({it.first, it.second + y[poz_y].second});
}
int poz_x = 0;
for(auto ity:y)
{
while(poz_x < x.size() && ity.first > x[poz_x].first + x[poz_x].second)
poz_x++;
if(poz_x == x.size())
break;
ll prec;
if(poz_x == 0) prec = 0;
else prec = x[poz_x - 1].first + 1;
if(prec + x[poz_x].second <= ity.first)
newy.push_back({ity.first - x[poz_x].second, x[poz_x].second + ity.second});
}
get_min(newx, newy);
return newx;
}
vector<pair<ll,ll>> dp[MAXN][MAXN];
std::vector<long long> calculate_necessary_time(
int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
std::vector<int> V, std::vector<long long> T)
{
for(int i=0;i<M;i++)
assert(C[i] - L[i] >= 0);
for(int dest=0;dest<N;dest++)
{
for(int i=0;i<N;i++)
invt[i][dest] = -1;
invt[dest][dest] = S - 1;
for(int pas=0;pas<N;pas++)
{
for(int i=0;i<M;i++)
{
for(auto [a,b] : vector<pair<int,int>>{{A[i], B[i]}, {B[i], A[i]}})
{
ll myt = min(invt[b][dest], C[i]);
if(myt - L[i] >= 0)
invt[a][dest] = max(invt[a][dest], myt - L[i]);
}
}
}
}
for(int src=0;src<N;src++)
{
for(int i=0;i<N;i++)
mint[src][i] = INF;
mint[src][src] = 0;
for(int pas=0;pas<N;pas++)
{
for(int i=0;i<M;i++)
{
for(auto [a,b] : vector<pair<int,int>>{{A[i], B[i]}, {B[i], A[i]}})
{
if(mint[src][a] % S <= C[i] - L[i])
{
mint[src][b] = min(mint[src][b], mint[src][a] + L[i]);
}
else
{
mint[src][b] = min(mint[src][b], (mint[src][a] + (S - mint[src][a] % S)) + L[i]);
}
}
}
}
}
vector<ll> ans(Q, INF);
vector<int> remaining;
for(int i=0;i<Q;i++)
{
if(invt[U[i]][V[i]] >= T[i])
{
remaining.push_back(i);
continue;
}
for(int stop=0;stop<N;stop++)
{
if(stop == V[i])
continue;
if(invt[U[i]][stop] >= T[i])
{
ll until_stop = S - T[i];
ll after_stop = mint[stop][V[i]];
ans[i] = min(ans[i], until_stop + after_stop);
}
}
}
for(int i=0;i<N;i++)
dp[i][i].push_back({S - 1, 0});
for(int i=0;i<M;i++)
{
for(auto [a,b] : vector<pair<int,int>>{{A[i], B[i]}, {B[i], A[i]}})
{
get_min(dp[a][b], apply_edge(dp[b][b], L[i], C[i]));
}
}
for(int k=0;k<N;k++)
{
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
get_min(dp[i][j], combine_chained(dp[i][k], dp[k][j]));
}
}
}
if(N > 60) return ans;//-----------------------------------------------------------------------
for(int i:remaining)
{
ans[i] = min(ans[i], query(dp[U[i]][V[i]], T[i]));
}
return ans;
}
