#include "nile.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
constexpr ll maxn = 1e5;
struct Node {
ll w, a, b;
bool operator<(const auto &a) const {
return w < a.w;
}
};
constexpr ll siz = (1 << 17);
constexpr ll inf = (1ll << 60);
pair<ll, ll> odd[siz * 2], par[siz * 2];
pair<ll, ll> query(int p, int l, int r, int sl, int sr, bool er_odd)
{
if (sl <= l && r <= sr) {
if (er_odd) return odd[p];
return par[p];
}
if (sl > r || sr < l) return {inf, -1};
int mid = (l + r) / 2;
return min(query(p * 2, l, mid, sl, sr, er_odd), query(p * 2 + 1, mid + 1, r, sl, sr, er_odd));
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
ll n = W.size();
vector<Node> noder(n);
for (ll i = 0; i < n; i++) noder[i] = {W[i], A[i], B[i]};
sort(noder.begin(), noder.end());
vector<Node> edges;
for (ll i = 0; i < n - 1; i++) edges.push_back({noder[i+1].w - noder[i].w, i, i+1});
sort(edges.begin(), edges.end());
vector<pair<ll, ll>> d(E.size());
for (int i = 0; i < (int) E.size(); i++) d[i] = {E[i], i};
sort(d.begin(), d.end());
for (int i = 0; i < n; i++)
{
if (i & 1) {
odd[i + siz] = {A[i] - B[i], i};
par[i + siz] = {inf, i};
} else {
odd[i + siz] = {inf, i};
par[i + siz] = {A[i] - B[i], i};
}
}
for (int y = n; y < siz; y++) odd[y + siz] = par[y + siz] = { inf, y};
for (int i = siz - 1; i > 0; i--)
{
odd[i] = min(odd[i * 2], odd[i * 2 + 1]);
par[i] = min(par[i * 2], par[i * 2 + 1]);
}
ll output = accumulate(A.begin(), A.end(), 0ll);
vector<ll> svar(E.size());
set<pair<ll, ll>> klumper;
for (int i = 0; i < n; i++) klumper.insert({i, i});
ll forbedring;
int neste_kant = 0;
for (auto [f, idx] : d)
{
while (neste_kant != n - 1 && edges[neste_kant].w <= f)
{
Node kant = edges[neste_kant++];
pair<ll, ll> venstre = *prev(klumper.upper_bound({kant.a, inf})),
hoyre = *klumper.lower_bound({kant.b, -1ll});
if (venstre.first == venstre.second && hoyre.first == hoyre.second)
{
output += B[venstre.first] - A[venstre.first] + B[hoyre.first] - A[hoyre.first];
klumper.erase(venstre);
klumper.erase(hoyre);
klumper.insert({venstre.first, hoyre.second});
} else if (venstre.first == venstre.second)
{
bool venstre_odd = (venstre.first & 1);
auto [val, ind] = query(1, 0, siz - 1, hoyre.first, hoyre.second, venstre_odd);
forbedring = A[venstre.first] - B[venstre.first] - val;
if (forbedring > 0)
{
output -= forbedring;
klumper.erase(venstre);
klumper.erase(hoyre);
klumper.insert({venstre.first, ind - 1});
klumper.insert({ind, ind});
if (ind != hoyre.second) klumper.insert({ind + 1, hoyre.second});
}
} else if (hoyre.first == hoyre.second)
{
bool hoyre_odd = (hoyre.first & 1);
auto [val, ind] = query(1, 0, siz - 1, venstre.first, venstre.second, hoyre_odd);
forbedring = A[hoyre.first] - B[hoyre.first] - val;
if (forbedring > 0)
{
output -= forbedring;
klumper.erase(venstre);
klumper.erase(hoyre);
klumper.insert({ind + 1, hoyre.first});
klumper.insert({ind, ind});
if (ind != venstre.first) klumper.insert({venstre.first, ind + 1});
}
} else
{
klumper.erase(venstre);
klumper.erase(hoyre);
klumper.insert({venstre.first, hoyre.second});
}
}
svar[idx] = output;
}
return svar;
}
