#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Artifact {
int w, a, b;
ll c;
};
struct Edge {
int diff, u, v, type;
bool operator<(const Edge& other) const {
return diff < other.diff;
}
};
struct DSU {
vector<int> parent;
vector<int> sz, L, R;
vector<ll> min_c[2]; // 0: even global index, 1: odd global index
vector<bool> has_type2;
ll current_extra_cost = 0;
DSU(int n, const vector<Artifact>& arts) {
parent.resize(n);
sz.assign(n, 1);
L.resize(n); R.resize(n);
has_type2.assign(n, false);
for(int i=0; i<2; ++i) min_c[i].assign(n, INF);
for (int i = 0; i < n; i++) {
parent[i] = i;
L[i] = R[i] = i;
min_c[i % 2][i] = arts[i].c;
current_extra_cost += arts[i].c;
}
}
int find(int i) {
return (parent[i] == i) ? i : (parent[i] = find(parent[i]));
}
ll get_min_unpaired(int r) {
if (sz[r] % 2 == 0) return 0;
// If size is odd, we must leave one out.
// If has_type2 is true, we can pick the absolute minimum C in the range.
// Otherwise, we can only pick C from indices with same parity as L[r].
ll res = min_c[L[r] % 2][r];
if (has_type2[r]) res = min(res, min_c[1 - (L[r] % 2)][r]);
return res;
}
void unite(int u, int v, int type) {
int root_u = find(u), root_v = find(v);
if (root_u == root_v) {
if (type == 2 && !has_type2[root_u]) {
current_extra_cost -= get_min_unpaired(root_u);
has_type2[root_u] = true;
current_extra_cost += get_min_unpaired(root_u);
}
return;
}
// Always merge into the smaller index/representative for range consistency
if (L[root_u] > L[root_v]) swap(root_u, root_v);
current_extra_cost -= get_min_unpaired(root_u);
current_extra_cost -= get_min_unpaired(root_v);
parent[root_v] = root_u;
sz[root_u] += sz[root_v];
L[root_u] = min(L[root_u], L[root_v]);
R[root_u] = max(R[root_u], R[root_v]);
has_type2[root_u] = has_type2[root_u] || has_type2[root_v] || (type == 2);
min_c[0][root_u] = min(min_c[0][root_u], min_c[0][root_v]);
min_c[1][root_u] = min(min_c[1][root_u], min_c[1][root_v]);
current_extra_cost += get_min_unpaired(root_u);
}
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size();
vector<Artifact> arts(n);
ll base_b_sum = 0;
for (int i = 0; i < n; i++) {
arts[i] = {W[i], A[i], B[i], (ll)A[i] - B[i]};
base_b_sum += B[i];
}
sort(arts.begin(), arts.end(), [](const Artifact& a, const Artifact& b) {
return a.w < b.w;
});
vector<Edge> edges;
for (int i = 0; i < n - 1; i++) {
edges.push_back({arts[i + 1].w - arts[i].w, i, i + 1, 1});
if (i < n - 2)
edges.push_back({arts[i + 2].w - arts[i].w, i, i + 2, 2});
}
sort(edges.begin(), edges.end());
vector<pair<int, int>> sorted_queries;
for (int i = 0; i < (int)E.size(); i++) sorted_queries.push_back({E[i], i});
sort(sorted_queries.begin(), sorted_queries.end());
DSU dsu(n, arts);
vector<ll> results(E.size());
int edge_idx = 0;
for (auto& q : sorted_queries) {
while (edge_idx < (int)edges.size() && edges[edge_idx].diff <= q.first) {
dsu.unite(edges[edge_idx].u, edges[edge_idx].v, edges[edge_idx].type);
edge_idx++;
}
results[q.second] = base_b_sum + dsu.current_extra_cost;
}
return results;
}
