#include "nile.h"
#include <algorithm>
#include <array>
#include <numeric>
#include <vector>
using namespace std;
struct DSU{
int n;
vector<int> par, sz;
vector<array<long long, 3>> info;
DSU(int N){
n = N;
par.assign(n, 0);
iota(par.begin(), par.end(), 0);
sz.assign(n, 1);
info.assign(n, {0});
}
int get_par(int v){
if (v == par[v])
return v;
return par[v] = get_par(par[v]);
}
long long onion_set(int a, int b, long long c = 0){
int order = a < b;
a = get_par(a);
b = get_par(b);
if (a != b){
if (sz[a] < sz[b])
swap(a, b);
long long pre = (sz[a] & 1) * min({info[a][0], info[a][1], info[a][2]});
pre += (sz[b] & 1) * min({info[b][0], info[b][1], info[b][2]});
sz[a] += sz[b];
par[b] = a;
if (order){
info[a][1] = info[b][1];
} else {
info[a][0] = info[b][0];
}
info[a][2] = min(info[a][2], info[b][2]);
long long post = (sz[a] & 1) * min({info[a][0], info[a][1], info[a][2]});
return post - pre;
} else {
long long pre = min({info[a][0], info[a][1], info[a][2]});
info[a][2] = min(info[a][2], c);
long long post = min({info[a][0], info[a][1], info[a][2]});
return (post - pre) * (sz[2] & 1);
}
return 0;
}
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = W.size();
int Q = E.size();
vector<int> order(N, 0);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b){
return W[a] < W[b];
});
vector<int> nW(N), nA(N), nB(N);
for (int i = 0; i < N; i++){
nW[i] = W[order[i]];
nA[i] = A[order[i]];
nB[i] = B[order[i]];
}
W = nW;
A = nA;
B = nB;
vector<int> order2(N-1);
iota(order2.begin(), order2.end(), 0);
sort(order2.begin(), order2.end(), [&](int a, int b){
return (W[a+1] - W[a]) < (W[b+1] - W[b]);
});
vector<int> order3(N-2);
iota(order3.begin(), order3.end(), 0);
sort(order3.begin(), order3.end(), [&](int a, int b){
return W[a+2] - W[a] < W[b+2] - W[b];
});
vector<int> order4(Q);
iota(order4.begin(), order4.end(), 0);
sort(order4.begin(), order4.end(), [&](int a, int b){
return E[a] < E[b];
});
long long base_ans = accumulate(B.begin(), B.end(), 0LL);
DSU dsu(N);
long long curr = 0;
for (int i = 0; i < N; i++){
A[i] = A[i] - B[i];
curr += A[i];
dsu.info[i] = {A[i], A[i], A[i]};
}
vector<long long> answer(Q, base_ans);
int i = 0, j = 0;
for (int idx : order4){
long long K = E[idx];
while (i < N-1 && W[order2[i]+1] - W[order2[i]] <= K){
curr += dsu.onion_set(order2[i], order2[i]+1);
i++;
}
while (j < N-2 && W[order3[j]+2] - W[order3[j]] <= K){
curr += dsu.onion_set(order3[j], order3[j]+2, W[order3[j]+1]);
j++;
}
answer[idx] += curr;
}
return answer;
}
