#include "overtaking.h"
#include <algorithm>
#include <utility>
#include <list>
#include <climits>
std::vector<std::vector<std::pair<long long, long long>>> SS(1001, std::vector<std::pair<long long, long long>>());
struct sort1
{
inline bool operator() (const std::pair<long long, int>& a, const std::pair<long long, int>& b)
{
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
};
class leaf
{
public:
leaf(long long _a, long long _b, long long _r)
{
a = _a;
b = _b;
r = _r;
}
long long a, b, r;
};
struct sort2
{
inline bool operator() (leaf const& a, leaf const& b)
{
return b.r < a.r;
}
};
int _M;
std::vector<int> _S;
int _X;
std::vector<leaf> ans;
std::vector<leaf> J(std::vector<leaf> & X)
{
std::vector<leaf> Y;
if (X.size() > 0)
{
std::sort(X.begin(), X.end(), sort2());
long long a, b, r = -1, ma = LLONG_MAX;
for (size_t i = 0; i < X.size(); i++)
{
if (X[i].r != r)
{
if (r == -1)
{
r = X[i].r;
a = X[i].a;
b = X[i].b;
}
else
{
if (ma > a)
{
if (b >= ma)
b = ma - 1;
Y.push_back(leaf(a, b, r));
ma = a;
}
r = X[i].r;
a = X[i].a;
b = X[i].b;
}
}
else
{
if (a > X[i].a)
a = X[i].a;
if (b < X[i].b)
b = X[i].b;
}
}
if (ma > a)
{
if (b >= ma)
b = ma - 1;
Y.push_back(leaf(a, b, r));
}
std::reverse(Y.begin(), Y.end());
}
return Y;
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
_X = X;
_M = M;
_S = S;
std::vector<std::pair<long long, int>> TW;
TW.reserve(N);
for (int i = 0; i < N; i++)
{
if (W[i] < X)
continue;
TW.push_back(std::make_pair(T[i], W[i]));
}
long long mb = 0;
std::vector<leaf> next;
std::vector<leaf> curr;
long long mr = 0;
int curr_i;
for (int j = 1; j < M; j++)
{
std::sort(TW.begin(), TW.end(), sort1());
mb = 0;
mr = 0;
curr_i = 0;
for (int i = 0; i < TW.size(); i++)
{
long long a = TW[i].first;
long long b = a + 1LL * (_S[j] - _S[j - 1]) * TW[i].second;
if (b < mb)
b = mb;
else
mb = b;
if (SS[j].size() == 0 || SS[j].back().second != b && (i + 1 == TW.size() || TW[i].first != TW[i + 1].first))
{
SS[j].push_back(std::make_pair(a, b));
long long fa = a - 1LL * X * _S[j - 1] + 1;
long long fb = b - 1LL * X * _S[j];
long long fc = b + 1LL * (_S[M - 1] - _S[j]) * X;
/*if (fc >= mr)
{
leaf front = leaf(fa, fb, fc);
ans.push_back(front);
}
else*/
{
leaf front = leaf(fa, fb, b);
next.push_back(front);
}
while (curr_i < curr.size())
{
if (curr[curr_i].r <= a)
{
long long fc = curr[curr_i].r + 1LL * (_S[M - 1] - _S[j - 1]) * X;
/*if (fc >= mr)
{
curr[curr_i].r = fc;
ans.push_back(curr[curr_i]);
curr_i++;
continue;
}*/
curr[curr_i].r = curr[curr_i].r + 1LL * (_S[j] - _S[j - 1]) * X;
next.push_back(curr[curr_i]);
curr_i++;
continue;
}
else
{
if (i + 1 == TW.size() || TW[i + 1].first > curr[curr_i].r)
{
long long fc = curr[curr_i].r + 1LL * (_S[j] - _S[j - 1]) * X;
if (fc < b)
fc = b;
curr[curr_i].r = fc;
next.push_back(curr[curr_i]);
curr_i++;
continue;
}
else
{
break;
}
}
}
}
long long c = b + 1LL * (_S[M - 1] - _S[j]) * TW[i].second;
if (mr < c)
mr = c;
TW[i].first = b;
}
while (curr_i < curr.size())
{
long long fc = curr[curr_i].r + 1LL * (_S[j] - _S[j - 1]) * X;
curr[curr_i].r = fc;
next.push_back(curr[curr_i]);
curr_i++;
}
curr = J(next);
}
while (curr.size() > 0)
{
ans.push_back(curr.back());
curr.pop_back();
}
ans = J(ans);
}
long long arrival_time(long long Y)
{
long long a = Y;
long long b = a + 1LL * _S[_M - 1] * _X;
if (ans.size() > 1 && ans[0].a <= a)
{
int l = 0, r = ans.size()-1;
while (l < r)
{
int m = (l + r + 1) / 2;
if (m == ans.size())
{
break;
}
else if (ans[m].a <= a)
{
l = m;
}
else
{
r = m - 1;
}
}
if (ans[l].b >= a)
b = ans[l].r;
}
return b;
}
