#include "nile.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
using II = pair<int,int>;
struct DisjointSet {
vector<int> par;
vector<int> sz;
int cnt_odd_size_comp;
DisjointSet(int _N) : par(_N, -1), sz(_N, 1), cnt_odd_size_comp(_N) {}
int find(int x) {
if (par[x] < 0) return x;
return par[x] = find(par[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
if (sz[x] < sz[y])
swap(x, y);
par[y] = x;
if (sz[y] % 2 == 1)
--cnt_odd_size_comp;
if (sz[x] % 2 == 1)
--cnt_odd_size_comp;
sz[x] += sz[y];
if (sz[x] % 2 == 1)
++cnt_odd_size_comp;
}
};
struct Artifact {
int weight;
int cost;
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B,
vector<int> E) {
// subtask 6: A[i] = 2, B[i] = 1
const int N = W.size();
if (N == 1)
return vector<long long>(N, A[0]);
long long base_cost = 0;
for (int i = 0; i < N; i++)
base_cost += B[i];
// cerr << "base_cost: " << base_cost << endl;
const int Q = E.size();
vector<long long> R(Q, base_cost);
vector<Artifact> artifacts;
for (int i = 0; i < N; i++)
artifacts.push_back({W[i], A[i] - B[i]});
sort(artifacts.begin(), artifacts.end(),
[&] (Artifact a, Artifact b) -> bool {return a.weight < b.weight; });
priority_queue< II, vector<II>, greater<II> > events;
for (int i = 0; i < N-1; ++i)
events.emplace( artifacts[i+1].weight - artifacts[i].weight, i );
priority_queue< II, vector<II>, greater<II> > sorted_queries;
for (int j = 0; j < Q; j++)
sorted_queries.emplace( E[j], j );
DisjointSet dset(N);
while (!sorted_queries.empty()) {
auto [e, j] = sorted_queries.top(); sorted_queries.pop();
while (!events.empty()) {
auto [wdif, i] = events.top();
if (wdif > e) break;
events.pop();
dset.join(i, i+1);
}
R[j] += dset.cnt_odd_size_comp;
}
return R;
}
