#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long) (1e9);
struct Info {
long long l = 0, r = INF, impair = INF, pair = INF, bonus = INF, ans = 0;
};
Info combine(Info a, Info b) {
Info nouv;
nouv.l = a.l;
nouv.r = b.r;
if ((a.r - a.l + 1) % 2 == 0) {
nouv.impair = min(a.impair, b.impair);
nouv.pair = min(a.pair, b.pair);
}
else {
nouv.impair = min(a.impair, b.pair);
nouv.pair = min(a.pair, b.impair);
}
nouv.bonus = min(a.bonus, b.bonus);
if ((nouv.r - nouv.l + 1) % 2 == 0) {
nouv.ans = 0;
}
else {
nouv.ans = min(nouv.impair, nouv.bonus);
}
return nouv;
}
class UnionFind {
public :
vector<Info> infos;
vector<long long> parent;
long long cur = 0;
long long tot = 0;
void create(Info nouv) {
infos.push_back(nouv);
parent.push_back(cur);
cur ++;
tot += nouv.ans;
}
long long racine(long long u) {
if (parent[u] == u)
return u;
parent[u] = racine(parent[u]);
return parent[u];
}
void merge(long long a, long long b) {
long long r1 = racine(a);
long long r2 = racine(b);
tot -= infos[r1].ans;
tot -= infos[r2].ans;
parent[r1] = cur;
parent[r2] = cur;
create(combine(infos[r1], infos[r2]));
return;
}
void bonif(long long ind, long long val) {
long long r1 = racine(ind);
tot -= infos[r1].ans;
infos[r1].bonus = min(infos[r1].bonus, val);
infos[r1].ans = min(infos[r1].ans, infos[r1].bonus);
tot += infos[r1].ans;
return;
}
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
vector<long long> w, a, b, e;
for (int i = 0; i < W.size(); i ++) {
w.push_back(W[i]);
a.push_back(A[i]);
b.push_back(B[i]);
}
for (int i = 0; i < E.size(); i ++) {
e.push_back(E[i]);
}
int n = w.size();
vector<pair<long long, long long>> artis(n, {0, 0});
long long rep = 0;
for (int i = 0; i < n; i ++) {
artis[i].first = w[i];
artis[i].second = a[i] - b[i];
rep += b[i];
}
sort(artis.begin(), artis.end());
vector<pair<long long, long long>> ans;
UnionFind goro;
for (int i = 0; i < n; i ++) {
Info nouv;
nouv.l = i;
nouv.r = i;
nouv.impair = artis[i].second;
nouv.ans = artis[i].second;
goro.create(nouv);
}
ans.push_back({0, goro.tot + rep});
vector<tuple<long long, long long, long long>> events;
for (int i = 0; i + 1 < n; i ++) {
events.push_back({artis[i + 1].first - artis[i].first, 0, i});
}
for (int i = 1; i + 1 < n; i ++) {
events.push_back({artis[i + 1].first - artis[i - 1].first, 1, i});
}
sort(events.begin(), events.end());
for (int i = 0; i < events.size(); i ++) {
if (get<1>(events[i]) == 0) {
goro.merge(get<2>(events[i]), get<2>(events[i]) + 1);
ans.push_back({get<0>(events[i]), goro.tot + rep});
}
else {
goro.bonif(get<2>(events[i]), artis[get<2>(events[i])].second);
ans.push_back({get<0>(events[i]), goro.tot + rep});
}
}
vector<long long> sus(e.size(), 0ll);
for (int i = 0; i < e.size(); i ++) {
long long lo = 0, hi = ans.size() - 1;
while (hi - lo > 1) {
long long mid = (lo + hi) / 2;
if (ans[mid].first <= e[i])
lo = mid;
else
hi = mid;
}
if (ans[hi].first <= e[i])
sus[i] = ans[hi].second;
else
sus[i] = ans[lo].second;
}
return sus;
}
