#include "overtaking.h"
#pragma GCC optimize( "O3,Ofast,unroll-loops" ) // de ce nu
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <map>
using ll = long long;
#define magic_sauce inline __attribute__((always_inline))
magic_sauce ll max( ll a, ll b ){ return a > b ? a : b; }
const int MAXN = 1000;
const int MAXM = 1000;
const ll INF = 1e18;
const ll NIL = -1;
struct Range {
ll begin;
ll val;
magic_sauce Range( ll a, ll b ) : begin( a ), val( b ) {}
};
struct Function {
std::vector<Range> ranges;
ll add;
magic_sauce ll operator ()( ll x ){
int st = 0, dr = (int)ranges.size(), mij;
while( dr - st > 1 ){
if( ranges[mij = (st + dr) >> 1].begin > x )
dr = mij;
else
st = mij;
}
if( ranges[st].val >= 0 )
return ranges[st].val;
return x + add;
}
// compunerea de functii
void operator *= ( Function &other ){
std::vector<Range> new_ranges;
int i, j, k, n = (int)ranges.size(), m = (int)other.ranges.size();;
int st, dr, mij;
ll start, end;
for( i = 0 ; i < n ; i++ ){
start = ranges[i].begin;
if( i + 1 < n )
end = ranges[i + 1].begin;
else
end = INF;
if( ranges[i].val >= 0 )
new_ranges.emplace_back( start, other( ranges[i].val ) );
else{
// functie liniara
// [start, end) -> [start + add, end + add)
// adaugam tot ce este in range-ul [it_start, it_end) doar ca + add
// tratam separat intervalul ce contine pe start
st = 0;
dr = m;
while( dr - st > 1 )
if( other.ranges[mij = (st + dr) >> 1].begin > start + add )
dr = mij;
else
st = mij;
j = st;
// cazul separat
new_ranges.emplace_back( start, other.ranges[j].val );
st = -1;
dr = m;
while( dr - st > 1 ){
if( other.ranges[mij = (st + dr) >> 1].begin < end + add )
st = mij;
else
dr = mij;
}
j++;
k = dr;
while( j < k ){
new_ranges.emplace_back( other.ranges[j].begin - add, other.ranges[j].val );
j++;
}
}
}
// prune next ranges
ranges = new_ranges;
add += other.add;
}
};
struct Solver {
int l, n, x, m;
std::vector<ll> t0; // timpul de pornire al autobuzelor
std::vector<int> speed; // s/m
std::vector<int> stat; // sorting station
ll dp[MAXM][MAXN];
std::map<ll, ll> slowest[MAXM];
Function f[MAXM];
void calc_dp(){
int i, j;
// facem ce spune enuntul
for( i = 0 ; i < n ; i++ )
dp[0][i] = t0[i];
for( i = 1 ; i < m ; i++ ){
// for( j = 0 ; j < n ; j++ )
// e[j] = dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]);
for( j = 0 ; j < n ; j++ )
slowest[i][dp[i - 1][j]] = max( slowest[i][dp[i - 1][j]], dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]) );
ll prev = -1;
for( auto p : slowest[i] ){
prev = max( slowest[i][p.first], prev );
slowest[i][p.first] = prev;
}
for( j = 0 ; j < n ; j++ ){
dp[i][j] = dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]);
auto it = slowest[i].lower_bound( dp[i - 1][j] );
if( it != slowest[i].begin() ){
it--;
dp[i][j] = max( dp[i][j], it->second );
}
}
}
}
void calc_map( int i ){
ll add = ((ll)x) * (stat[i] - stat[i - 1]);
f[i].add = add;
// daca am ajuns primii suntem liberi sa facem ce vrem
f[i].ranges.emplace_back( 0, NIL );
auto it = slowest[i].begin();
auto next = it;
while( it != slowest[i].end() ){
next++;
ll start = it->first;
ll cand = it->second;
ll end = INF;
if( next != slowest[i].end() )
end = next->first;
start++;
end++;
// [start, cand - add) -> t' = cand
// [cand - add, end) -> t' = t + add
ll mij = cand - add;
if( start < mij )
f[i].ranges.emplace_back( start, cand );
else
mij = start;
if( mij < end )
f[i].ranges.emplace_back( mij, NIL );
it = next;
}
}
void compress_maps(){
for( int p2 = 1 ; p2 < 1024 ; p2 <<= 1 )
for( int i = 1 ; i + p2 < m ; i += (p2 << 1) )
f[i] *= f[i + p2];
}
void pre(){
// using the dp from the statement we precalculate the positions of the other bussesx
calc_dp();
// the old query function is a repeated aplication of M functions (in the math sense)
// therefore we can hold these functions as a reunion of several intervals
// each being either a constant function or a linear function with slope 1
for( int i = 1 ; i < m ; i++ )
calc_map( i );
compress_maps();
}
ll query( ll t ){
return f[1]( t );
}
} sol;
void init( int L, int N, std::vector<ll> T, std::vector<int> W, int X, int M, std::vector<int> S ){
// first of all, anything faster than x doesn't matter
// therefore we can assume that the special bus in the
// fastest one and the others are slowing it down
// each buss has to worry only about the ones slower than itsself
// for this exact reason, all the busse's paths (exept N) are predetermined
// some precalculation
sol.l = L;
sol.n = N;
sol.x = X;
sol.m = M;
sol.t0 = T;
sol.speed = W;
sol.stat = S;
sol.pre();
}
ll arrival_time( ll Y ){
return sol.query( Y );
return 0;
}
