#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
template<typename T> void cmin(T& x, T y) { x = min(x, y); }
constexpr int MAX_W = int(1e9);
struct segment_info {
int size;
int best_active = MAX_W;
array<int, 2> best_passive{MAX_W, MAX_W};
};
segment_info merge(segment_info l, segment_info r) {
int parity = l.size % 2;
cmin(l.best_active, r.best_active);
cmin(l.best_passive[0], r.best_passive[parity]);
cmin(l.best_passive[1], r.best_passive[!parity]);
l.size += r.size;
return l;
}
struct DSU {
vector<int> link, right;
vector<segment_info> info;
DSU(vector<int> sizes) {
int n = int(sizes.size());
link.resize(n);
iota(link.begin(), link.end(), 0);
right = link;
info.resize(n);
for (int i = 0; i < n; ++i) info[i].size = sizes[i];
}
int get(int x) {
return link[x] = (link[x] == x ? x : get(link[x]));
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
if (x > y) swap(x, y);
info[x] = merge(info[x], info[y]);
right[x] = y;
link[y] = x;
return true;
}
int cost(int v) {
v = get(v);
if (info[v].size % 2 == 0) return 0;
return min(info[v].best_active, info[v].best_passive[0]);
}
};
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int N = int(W.size());
int Q = int(E.size());
vector<int> coords = W;
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());
int s = int(coords.size());
vector<int> min_d(s, MAX_W);
vector<int> sizes(s);
for (int i = 0; i < N; ++i) {
int id = int(lower_bound(coords.begin(), coords.end(), W[i]) - coords.begin());
min_d[id] = min(min_d[id], A[i] - B[i]);
sizes[id]++;
}
DSU dsu(sizes);
for (int i = 0; i < s; ++i) {
if (sizes[i] == 1) {
dsu.info[i].best_passive[0] = min_d[i];
} else {
dsu.info[i].best_active = min_d[i];
}
}
vector<array<int, 2>> events;
for (int i = 0; i < s - 1; ++i) {
events.push_back({coords[i + 1] - coords[i], i});
}
for (int i = 1; i < s - 1; ++i) {
events.push_back({coords[i + 1] - coords[i - 1], ~i});
}
sort(events.begin(), events.end());
int64_t sum = accumulate(B.begin(), B.end(), int64_t(0));
int64_t cur_ans = 0;
for (int i = 0; i < s; ++i) cur_ans += dsu.cost(i);
vector<int> q_ord(Q);
iota(q_ord.begin(), q_ord.end(), 0);
sort(q_ord.begin(), q_ord.end(), [&](int x, int y) {
return E[x] < E[y];
});
vector<long long> ans(Q);
int ans_p = 0;
for (auto[t, e] : events) {
while (ans_p < Q && E[q_ord[ans_p]] < t) {
ans[q_ord[ans_p++]] = cur_ans + sum;
}
if (e < 0) {
e = ~e;
int l = dsu.get(e);
cur_ans -= dsu.cost(l);
cmin(dsu.info[l].best_active, min_d[e]);
cur_ans += dsu.cost(l);
} else {
cur_ans -= dsu.cost(e) + dsu.cost(e + 1);
dsu.unite(e, e + 1);
cur_ans += dsu.cost(e);
}
}
while (ans_p < Q) ans[q_ord[ans_p++]] = cur_ans + sum;
return ans;
}
