#include "bits/stdc++.h"
#include "nile.h"
using namespace std;
const int INF = 1e9;
// Augmented DSU: we store more info per component (like min cost and index)
struct DSU {
vector<int> e; // parent array (negative means root and holds size)
vector<int> c; // c[i] = A[i] - B[i]
vector<int> mni; // smallest index in component (for parity decisions)
vector<array<int, 3>> mnc; // mnc[i][0/1/2] = min cost for parity 0/1/unpaired
long long tot = 0; // extra cost to add to baseline
DSU(int n, vector<int> c) : e(n, -1), c(c), mni(n), mnc(n) {
for (int i = 0; i < n; ++i) {
mni[i] = i;
mnc[i] = {INF, INF, INF}; // large default
mnc[i][i % 2] = c[i]; // set A[i]-B[i] based on index parity
tot += c[i]; // initially all artifacts go alone
}
}
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
int size(int x) { return -e[find(x)]; }
// Computes extra cost for a group rooted at x
int cost(int x) {
int idx = mnc[x][mni[x] % 2] < mnc[x][2] ? (mni[x] % 2) : 2;
return mnc[x][idx] * (size(x) % 2); // pay only if group has odd size
}
bool join(int i, int j) {
int x = find(i), y = find(j);
if (x == y) {
tot -= cost(x); // remove old cost
mnc[x][2] = min(mnc[x][2], c[(i + j) / 2]); // update fallback
tot += cost(x); // add new cost
return false;
}
tot -= cost(x);
tot -= cost(y);
if (e[x] > e[y]) swap(x, y); // merge small into large
e[x] += e[y];
e[y] = x;
for (int p = 0; p < 3; ++p) mnc[x][p] = min(mnc[x][p], mnc[y][p]);
mni[x] = min(mni[x], mni[y]);
tot += cost(x);
return true;
}
};
// Main function using offline queries and edge merging
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size(), q = E.size();
// Sort artifacts by weight
vector<int> ordW(n);
iota(ordW.begin(), ordW.end(), 0);
sort(ordW.begin(), ordW.end(), [&](int i, int j) {
return W[i] < W[j];
});
// Sort queries by D
vector<int> ordE(q);
iota(ordE.begin(), ordE.end(), 0);
sort(ordE.begin(), ordE.end(), [&](int i, int j) {
return E[i] < E[j];
});
vector<int> w(n), c(n); // remapped weights and A-B costs
for (int i = 0; i < n; ++i) {
int j = ordW[i];
w[i] = W[j];
c[i] = A[j] - B[j];
}
// Precompute edges: (weight difference, index1, index2)
vector<array<int, 3>> edges;
for (int i = 0; i < n; ++i) {
if (i + 1 < n) edges.push_back({w[i + 1] - w[i], i, i + 1});
if (i + 2 < n) edges.push_back({w[i + 2] - w[i], i, i + 2});
}
sort(edges.rbegin(), edges.rend()); // descending for efficient pop_back()
// Initialize DSU and base cost (everyone goes in a boat together: sum B[i])
DSU d(n, c);
vector<long long> R(q, accumulate(B.begin(), B.end(), 0LL));
// Process queries in increasing order of D
for (int i = 0; i < q; ++i) {
while (!edges.empty() && edges.back()[0] <= E[ordE[i]]) {
auto [_, x, y] = edges.back(); edges.pop_back();
d.join(x, y); // merge if allowed
}
R[ordE[i]] += d.tot; // add extra cost of lone artifacts in odd groups
}
return R;
}
