Submission #1197165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197165		badge881	Nile (IOI24_nile)	C++20	100 / 100	67 ms	8128 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct UFD {
    vector<int> boss, size;
    vector<int> even, odd;
    ll cost = 0;

    UFD(vector<int> &A, vector<int> &B) : boss(A.size(), -1), size(A.size(), 1), even(A.size()), odd(A.size(), INT_MAX) {
        for (int i = 0; i < A.size(); i++) {
            even[i] = A[i] - B[i];
            cost += even[i];
        }
    }
    int getBoss(int x) {
        return ~boss[x] ? boss[x] = getBoss(boss[x]) : x;
    }
    void merge(int v) {
        int u = getBoss(v - 1);
        for (int x : {u, v})
            if (size[x] & 1)
                cost -= even[x];

        if (size[u] & 1)
            swap(even[v], odd[v]);
        odd[u] = min(odd[u], odd[v]);
        even[u] = min(even[u], even[v]);

        boss[v] = u;
        size[u] += size[v];
        if (size[u] & 1)
            cost += even[u];
    }
    void calcul(int v, int w) {
        int u = getBoss(v);
        if (v - u & 1) {
            if (size[u] & 1)
                cost -= even[u];
            even[u] = min(even[u], w);
            if (size[u] & 1)
                cost += even[u];
        }
        else
            odd[u] = min(odd[u], w);
    }
};

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size(), q = E.size();
    if (n == 1)
        return vector<ll>(q, A[0]);

    vector<tuple<int, int, int>> helper;
    for (int i = 0; i < n; i++)
        helper.push_back({W[i], A[i], B[i]});
    sort(helper.begin(), helper.end());
    for (int i = 0; i < n; i++)
        tie(W[i], A[i], B[i]) = helper[i];

    vector<int> diff1(n - 1);
    iota(diff1.begin(), diff1.end(), 1);
    sort(diff1.begin(), diff1.end(), [&](int i, int j) {
        return W[i] - W[i - 1] < W[j] - W[j - 1];
    });

    vector<int> diff2(n - 2);
    iota(diff2.begin(), diff2.end(), 1);
    sort(diff2.begin(), diff2.end(), [&](int i, int j) {
        return W[i + 1] - W[i - 1] < W[j + 1] - W[j - 1];
    });

    vector<int> indexes(q);
    iota(indexes.begin(), indexes.end(), 0);
    sort(indexes.begin(), indexes.end(), [&](int i, int j) {
        return E[i] < E[j];
    });

    UFD ufd(A, B);
    int p1 = 0, p2 = 0;
    vector<ll> costs(q);
    ll total = accumulate(B.begin(), B.end(), 0LL);
    for (int index : indexes) {
        while (p1 < n - 1 && W[diff1[p1]] - W[diff1[p1] - 1] <= E[index]) {
            int idx = diff1[p1++];
            ufd.merge(idx);

            for (int p : {idx, idx - 1})
                if (p && p < n - 1 && W[p + 1] - W[p - 1] <= E[index] && ufd.getBoss(p + 1) == ufd.getBoss(p - 1))
                    ufd.calcul(p, A[p] - B[p]);
        }
        while (p2 < n - 2 && W[diff2[p2] + 1] - W[diff2[p2] - 1] <= E[index]) {
            int idx = diff2[p2++];
            if (ufd.getBoss(idx + 1) == ufd.getBoss(idx - 1))
                ufd.calcul(idx, A[idx] - B[idx]);
        }
        costs[index] = total + ufd.cost;
    }

    return costs;
}

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