| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1317268 | foxserg | 나일강 (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int MAXN = 100000;
int pred[MAXN];
int sz[MAXN];
int min_c[MAXN];
ll cur_add = 0;
int get(int v) {
if (v == pred[v]) return v;
return pred[v] = get(pred[v]);
}
void unite(int v, int u) {
v = get(v);
u = get(u);
if (sz[v] > sz[u]) swap(v, u);
if (sz[v] & 1) cur_add -= min_c[v];
if (sz[u] & 1) cur_add -= min_c[u];
pred[v] = u;
sz[u] += sz[v];
min_c[u] = min(min_c[u], min_c[v]);
if (sz[u] & 1) cur_add += min_c[u];
}
vector <ll> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> E) {
struct event {
int t; // 0 - update, 1 - get
int ind;
int d;
event(int t, int ind, int d): t(t), ind(ind), d(d) {}
bool operator<(const event &oth) const {
return tie(d, t) < tie(oth.d, oth.t);
}
};
int n = A.size();
fill(sz, sz + n, 1);
iota(pred, pred + n, 0);
vector <event> es;
for (int i = 0; i < E.size(); ++i) {
es.push_back(event(1, i, E[i]));
}
int p[n];
iota(p, p + n, 0);
sort(p, p + n, [&](int i, int j) {
return W[i] < W[j];
});
for (int i = 1; i < n; ++i) {
es.push_back(event(0, i - 1, abs(W[p[i]] - W[p[i - 1]])));
}
vector <int> C(n);
for (int i = 0; i < n; ++i) C[i] = A[i] - B[i];
for (int i = 0; i < n; ++i) min_c[i] = C[i];
for (int i = 0; i < n; ++i) cur_add += C[i];
ll sm = 0;
for (int i = 0; i < n; ++i) {
sm += B[i];
}
sort(es.begin(), es.end());
vector <ll> ans(E.size());
for (event e : es) {
if (e.t == 0) {
unite(p[e.ind], p[e.ind + 1]);
} else if (e.t == 1) {
ans[e.ind] = sm + cur_add;
}
}
return ans;
}