#include "nile.h"
#include <algorithm>
#include <functional>
#include <numeric>
#include <set>
typedef long long ll;
struct Item {
ll w, del;
};
struct Query {
ll e, i;
};
std::vector<ll> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
const ll n = W.size();
std::vector<Item> items(n);
ll sum_a = 0;
for (ll i = 0; i < n; ++i) {
items[i] = {W[i], A[i] - B[i]};
sum_a += A[i];
}
std::sort(items.begin(), items.end(),
[](Item a, Item b) { return a.w < b.w; });
std::vector<Query> queries;
for (ll i = 0; i < E.size(); ++i) {
queries.push_back({E[i], i});
}
std::sort(queries.begin(), queries.end(),
[](Query a, Query b) { return a.e < b.e; });
std::set<std::pair<ll, ll>> merge_ranges;
for (ll i = 1; i < n; ++i) {
merge_ranges.insert({items[i].w - items[i - 1].w, i});
}
std::set<std::pair<ll, ll>> add_elements;
for (ll i = 1; i < n - 1; ++i) {
add_elements.insert({items[i + 1].w - items[i - 1].w, i});
}
// the set of all odd/even positioned elements satisfying W[i+1] - W[i-1] <= e
std::vector<ll> min_odd(n, 1e15), min_even(n, 1e15), odd(n, 1e15), even(n);
std::vector<ll> par(n), sz(n, 1), contrib(n), tot(n);
std::iota(par.begin(), par.end(), 0LL);
ll cur = 0;
for (ll i = 0; i < n; ++i) {
even[i] = tot[i] = items[i].del;
}
std::function<ll(ll)> root;
root = [&](ll x) { return x == par[x] ? x : par[x] = root(par[x]); };
std::function<void(ll)> update;
auto merge = [&](ll x, ll y) {
x = root(x);
y = root(y);
if (x == y) {
return;
}
if (x > y) {
std::swap(x, y);
}
if (sz[x] % 2 == 0) {
min_odd[x] = std::min(min_odd[x], min_odd[y]);
min_even[x] = std::min(min_even[x], min_even[y]);
odd[x] = std::min(odd[x], odd[y]);
even[x] = std::min(even[x], even[y]);
} else {
min_odd[x] = std::min(min_odd[x], min_even[y]);
min_even[x] = std::min(min_even[x], min_odd[y]);
odd[x] = std::min(odd[x], even[y]);
even[x] = std::min(even[x], odd[y]);
}
sz[x] += sz[y], sz[y] = 0;
tot[x] += tot[y], tot[y] = 0;
par[y] = x;
cur -= contrib[x] + contrib[y], contrib[x] = contrib[y] = 0;
update(x);
};
update = [&](ll x) {
contrib[x] = tot[x];
if (sz[x] % 2 == 1) {
contrib[x] -= std::min(
{items[x].del, items[x + sz[x] - 1].del, min_odd[x], even[x]});
}
cur += contrib[x];
};
std::vector<ll> answers(E.size());
for (auto &[e, i] : queries) {
while (!add_elements.empty() and add_elements.begin()->first <= e) {
auto i = add_elements.begin()->second;
auto r = root(i);
if ((i - r) % 2 == 0) {
min_even[r] = std::min(min_even[r], items[i].del);
} else {
min_odd[r] = std::min(min_odd[r], items[i].del);
}
cur -= contrib[r];
update(r);
add_elements.erase(add_elements.begin());
}
while (!merge_ranges.empty() and merge_ranges.begin()->first <= e) {
auto i = merge_ranges.begin()->second;
merge(i, i - 1);
merge_ranges.erase(merge_ranges.begin());
}
answers[i] = sum_a - cur;
}
return answers;
}
