#include "nile.h"
#include <vector>
#include <algorithm>
#include <climits>
using ll = long long;
static const ll NEG_INF = -(1LL<<60);
struct Matrix {
// max-plus 2x2 matrix
ll a[2][2];
};
// multiply B * A in max-plus semiring
static Matrix mul(const Matrix &B, const Matrix &A) {
Matrix C;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
ll v = NEG_INF;
for(int k = 0; k < 2; k++) {
v = std::max(v, B.a[i][k] + A.a[k][j]);
}
C.a[i][j] = v;
}
}
return C;
}
std::vector<long long> calculate_costs(
std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int N = W.size();
int Q = E.size();
std::vector<ll> result(Q, 0);
// sum of sending alone costs
ll sumA = 0;
for(int i = 0; i < N; i++) sumA += A[i];
if(N == 1) {
// only one artifact: always alone
for(int j = 0; j < Q; j++) result[j] = sumA;
return result;
}
// sort artifacts by weight
struct Item { int w; ll delta; };
std::vector<Item> items(N);
for(int i = 0; i < N; i++) {
items[i].w = W[i];
items[i].delta = (ll)A[i] - (ll)B[i];
}
std::sort(items.begin(), items.end(), [](auto &x, auto &y){ return x.w < y.w; });
// compute gaps
std::vector<std::pair<int,int>> gaps;
gaps.reserve(N-1);
for(int i = 0; i < N-1; i++) {
int g = items[i+1].w - items[i].w;
gaps.emplace_back(g, i+1); // edge index = i+1
}
std::sort(gaps.begin(), gaps.end(), [](auto &x, auto &y){ return x.first < y.first; });
// prepare queries
std::vector<std::pair<int,int>> queries(Q);
for(int j = 0; j < Q; j++) queries[j] = {E[j], j};
std::sort(queries.begin(), queries.end());
// segment tree over edges 1..N-1, size = next pow2 of N
int sz = 1;
while(sz < N) sz <<= 1;
std::vector<Matrix> seg(2*sz);
// identity matrix
Matrix I;
I.a[0][0] = 0; I.a[0][1] = NEG_INF;
I.a[1][0] = NEG_INF; I.a[1][1] = 0;
// off-edge matrix
Matrix Off;
Off.a[0][0] = NEG_INF; Off.a[0][1] = 0;
Off.a[1][0] = NEG_INF; Off.a[1][1] = 0;
// initialize leaves
for(int i = 0; i < sz; i++) {
if(i >= 1 && i < N) seg[sz + i] = Off;
else seg[sz + i] = I;
}
// build
for(int i = sz-1; i >= 1; i--) {
seg[i] = mul(seg[2*i+1], seg[2*i]);
}
// sweep gaps and queries
int ptr = 0;
for(auto &q : queries) {
int D = q.first, qid = q.second;
// activate all gaps with g <= D
while(ptr < (int)gaps.size() && gaps[ptr].first <= D) {
int k = gaps[ptr].second; // edge index
// build On matrix for this k
Matrix On;
On.a[0][0] = NEG_INF; On.a[0][1] = 0;
ll wsum = items[k].delta + items[k-1].delta;
On.a[1][0] = wsum; On.a[1][1] = 0;
// update leaf at pos k
int pos = sz + k;
seg[pos] = On;
// rebuild up
pos >>= 1;
while(pos >= 1) {
seg[pos] = mul(seg[2*pos+1], seg[2*pos]);
pos >>= 1;
}
ptr++;
}
// root stores product of all M; initial state [0,0]
// matched sum = max(root.a[1][0]+0, root.a[1][1]+0)
ll matched = std::max(seg[1].a[1][0], seg[1].a[1][1]);
result[qid] = sumA - matched;
}
return result;
}
