제출 #1317260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317260		foxserg	나일강 (IOI24_nile)	C++20	38 / 100	52 ms	8608 KiB

nile

#include <bits/stdc++.h>

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]) std::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] = std::min(min_c[u], min_c[v]);

    if (sz[u] & 1) cur_add += min_c[u];
}

std::vector <ll> calculate_costs(std::vector <int> W, std::vector <int> A, std::vector <int> B, std::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 std::tie(d, t) < std::tie(oth.d, oth.t);
        }
    };

    int n = A.size();

    std::fill(sz, sz + n, 1);
    std::iota(pred, pred + n, 0);

    std::vector <event> es;
    for (int i = 0; i < E.size(); ++i) {
        es.push_back(event(1, i, E[i]));
    }

    int p[n];
    std::iota(p, p + n, 0);
    std::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]])));
    }

    std::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[p[i]];
    for (int i = 0; i < n; ++i) cur_add += C[p[i]];

    ll sm = 0;
    for (int i = 0; i < n; ++i) {
        sm += B[i];
    }
    sort(es.begin(), es.end());

    std::vector <ll> ans(E.size());
    for (event e : es) {
        if (e.t == 0) {
            unite(e.ind, e.ind + 1);
        } else if (e.t == 1) {
            ans[e.ind] = sm + cur_add;
        }
    }

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18