#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;
struct DSU {
vector<long long> par, size, mn_odd, mn_even, ans, costs;
long long sum = 0;
DSU(long long n, vector<long long> C) : par(n), size(n, 1), mn_odd(C), ans(C), costs(C) {
mn_even.assign(n, INT_MAX);
sum = accumulate(all(C), 0LL);
iota(all(par), 0);
}
long long find(long long u) {
return par[u] == u ? u : par[u] = find(par[u]);
}
void add(long long u) {
u = find(u);
if (size[u] & 1) sum += ans[u];
}
void subtract(long long u) {
u = find(u);
if (size[u] & 1) sum -= ans[u];
}
void merge(long long u, long long v) {
if (v-u == 1) {
u = find(u), v = find(v);
subtract(u);
subtract(v);
if (size[u] & 1) {
swap(mn_odd[v], mn_even[v]);
}
mn_odd[u] = min(mn_odd[u], mn_odd[v]);
mn_even[u] = min(mn_even[u], mn_even[v]);
ans[u] = min(ans[u], mn_odd[u]);
ans[u] = min(ans[u], ans[v]);
par[v] = u;
size[u] += size[v];
add(u);
} else {
long long r = find(u);
subtract(r);
ans[r] = min(ans[r], costs[u+1]);
add(r);
}
}
};
vector<long long> calculate_costs(
vector<int> W, vector<int> A,
vector<int> B, vector<int> E
) {
int n = W.size(), q = E.size();
vector<int> ind_W(n);
iota(all(ind_W), 0);
sort(all(ind_W), [&](int i, int j) { return W[i] < W[j]; });
vector<int> new_W(n);
vector<long long> C(n);
for (int i = 0; i < n; i++) {
new_W[i] = W[ind_W[i]];
C[i] = A[ind_W[i]] - B[ind_W[i]];
}
swap(new_W, W);
vector<int> ind_E(q);
iota(all(ind_E), 0);
sort(all(ind_E), [&](int i, int j) { return E[i] < E[j]; });
vector<array<int, 3>> edges;
for (int i = 0; i < n-1; i++) {
edges.push_back({W[i+1] - W[i], i, i+1});
if (i+2 < n) edges.push_back({W[i+2] - W[i], i, i+2});
}
sort(all(edges));
DSU D(n, C);
int ptr = 0;
long long sum_B = accumulate(all(B), 0LL);
vector<long long> ans(q);
for (int i : ind_E) {
while (ptr < edges.size() && edges[ptr][0] <= E[i]) {
int u = edges[ptr][1];
int v = edges[ptr][2];
D.merge(u, v);
ptr++;
}
ans[i] = D.sum + sum_B;
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |