#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = signed;
constexpr int INF = 2e18;
struct Query {
int dis, id_qry;
auto operator<=>(const Query&) const = default;
};
struct Artifact {
int weight, value;
auto operator<=>(const Artifact&) const = default;
};
struct Interval {
int sum_values = 0, cnt_arts = 0;
int min_even = INF, min_odd = INF, min_skipped = INF;
int compute() {
if (cnt_arts % 2 == 0)
return sum_values;
else
return sum_values - min(min_even, min_skipped);
}
static Interval singleton(int value) {
return {value, 1, value, INF, INF};
}
};
Interval combine(Interval I, Interval J) {
if (I.cnt_arts % 2)
swap(J.min_even, J.min_odd);
return {
I.sum_values + J.sum_values,
I.cnt_arts + J.cnt_arts,
min(I.min_even, J.min_even),
min(I.min_odd, J.min_odd),
min(I.min_skipped, J.min_skipped)
};
}
struct UF { // path compression only
vector<int> repr;
vector<Interval> info;
int cur_answer = 0;
UF(const vector<Artifact> &arts) {
repr.resize(arts.size());
iota(repr.begin(), repr.end(), 0);
for (auto &art : arts)
info.push_back(Interval::singleton(art.value));
}
int find(int x) {
if (x != repr[x]) repr[x] = find(repr[x]);
return repr[x];
}
void merge(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
assert(x < y);
cur_answer -= info[x].compute() + info[y].compute();
info[x] = combine(info[x], info[y]);
cur_answer += info[x].compute();
repr[y] = x;
}
};
enum EventType { MERGE_ONE, MERGE_TWO, QUERY };
struct Event {
int dis; EventType mode; int mode_arg; // {i, i+1}, {i, i+2} or id_qry
auto operator<=>(const Event&) const = default;
};
vector<int> solve(vector<Artifact> arts, vector<Query> queries) {
vector<int> answer(queries.size(), 0);
sort(arts.begin(), arts.end());
int nb_arts = arts.size();
vector<Event> events;
for (int i = 0; i < nb_arts-1; ++i) {
auto &cur = arts[i], &nxt1 = arts[i+1];
events.push_back({nxt1.weight - cur.weight, MERGE_ONE, i});
if (i < nb_arts-2) {
auto &nxt2 = arts[i+2];
events.push_back({nxt2.weight - cur.weight, MERGE_TWO, i});
}
}
for (auto &[dis, id_qry] : queries)
events.push_back({dis, QUERY, id_qry});
sort(events.begin(), events.end());
UF uf(arts);
for (auto &[dis, ev_typ, ev_arg] : events) {
if (ev_typ == MERGE_ONE) {
uf.merge(ev_arg, ev_arg+1);
} else if (ev_typ == MERGE_TWO) {
int jumped_over = ev_arg+1; // arg->arg+2
auto &itv = uf.info[uf.find(jumped_over)];
uf.cur_answer -= itv.compute();
itv.min_skipped = min(itv.min_skipped, arts[jumped_over].value);
uf.cur_answer += itv.compute();
} else {
assert(ev_typ == QUERY);
answer[ev_arg] = uf.cur_answer;
}
}
return answer;
}
vector<int> calculate_costs(vector<i32> W, vector<i32> A, vector<i32> B, vector<i32> E) {
int nb_artifacts = W.size(), nb_queries = E.size();
vector<Artifact> artifacts;
for (int i = 0; i < nb_artifacts; ++i) {
artifacts.push_back({W[i], A[i] - B[i]});
}
vector<Query> queries;
for (int i = 0; i < nb_queries; ++i) {
queries.push_back({E[i], i});
}
vector<int> answer = solve(artifacts, queries);
int sum_A = accumulate(A.begin(), A.end(), 0ll);
for (int &x : answer) {
x = sum_A - x;
}
return answer;
}
