Submission #1255967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255967		farhan11679	Nile (IOI24_nile)	C++20	100 / 100	82 ms	19880 KiB

nile

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

struct DSU {
    int n;
    vector<int> p, sz, minIndex;
    vector<ll> minC_par[2], minEnabled;

    DSU(int _n=0): n(_n), p(n), sz(n), minIndex(n), minEnabled(n, (ll)9e18) {
        for(int i=0; i<n; i++) {
            p[i] = i;
            sz[i] = 1;
            minIndex[i] = i;
        }
        minC_par[0] = vector<ll>(n, (ll)9e18);
        minC_par[1] = vector<ll>(n, (ll)9e18);
    }

    int find(int a) {
        return p[a] == a ? a : p[a] = find(p[a]);
    }

    void unite_roots(int ra, int rb) {
        if (ra == rb) return;
        if (sz[ra] < sz[rb]) swap(ra, rb);
        p[rb] = ra;
        sz[ra] += sz[rb];
        minIndex[ra] = min(minIndex[ra], minIndex[rb]);
        for(int par = 0; par < 2; par++) {
            minC_par[par][ra] = min(minC_par[par][ra], minC_par[par][rb]);
        }
        minEnabled[ra] = min(minEnabled[ra], minEnabled[rb]);
    }
};

vector<ll> calculate_costs(
    vector<int> W,
    vector<int> A,
    vector<int> B,
    vector<int> E
) {
    int N = W.size();
    int Q = E.size();
    vector<ll> w(N), a(N), b(N), e(Q);
    for (int i = 0; i < N; i++) w[i] = W[i], a[i] = A[i], b[i] = B[i];
    for (int i = 0; i < Q; i++) e[i] = E[i];

    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j){
        return w[i] < w[j] || (w[i] == w[j] && i < j);
    });

    vector<ll> sW(N), sA(N), sB(N);
    for (int i = 0; i < N; i++) {
        sW[i] = w[ord[i]];
        sA[i] = a[ord[i]];
        sB[i] = b[ord[i]];
    }

    vector<ll> C(N);
    ll sumB = 0;
    for (int i = 0; i < N; i++) {
        C[i] = sA[i] - sB[i];
        sumB += sB[i];
    }

    struct PairItem { ll diff; int i, j; int type; };
    vector<PairItem> pairs;
    for (int i = 0; i + 1 < N; i++) {
        pairs.push_back({ sW[i+1] - sW[i], i, i+1, 1 });
    }
    for (int i = 0; i + 2 < N; i++) {
        pairs.push_back({ sW[i+2] - sW[i], i, i+2, 2 });
    }
    sort(pairs.begin(), pairs.end(), [](const PairItem& A, const PairItem& B) {
        if (A.diff != B.diff) return A.diff < B.diff;
        return A.type < B.type;
    });

    vector<int> qidx(Q);
    iota(qidx.begin(), qidx.end(), 0);
    sort(qidx.begin(), qidx.end(), [&](int i, int j) {
        if (e[i] != e[j]) return e[i] < e[j];
        return i < j;
    });

    DSU dsu(N);
    for (int i = 0; i < N; i++) {
        dsu.minC_par[ i & 1 ][i] = C[i];
    }

    auto comp_contrib = [&](int root) {
        if (dsu.sz[root] % 2 == 0) return 0LL;
        int L = dsu.minIndex[root];
        int par = L & 1;
        ll best = min(dsu.minC_par[par][root], dsu.minEnabled[root]);
        return best;
    };

    ll extra_sum = 0;
    for (int i = 0; i < N; i++) extra_sum += C[i];

    vector<char> enabled(N, 0);
    int pptr = 0;
    vector<ll> ans(Q);

    for (int qi = 0; qi < Q; qi++) {
        int qi0 = qidx[qi];
        ll D = e[qi0];
        while (pptr < (int)pairs.size() && pairs[pptr].diff <= D) {
            auto &pr = pairs[pptr];
            if (pr.type == 2) {
                int mid = pr.i + 1;
                if (!enabled[mid]) {
                    enabled[mid] = 1;
                    int r = dsu.find(mid);
                    extra_sum -= comp_contrib(r);
                    dsu.minEnabled[r] = min(dsu.minEnabled[r], C[mid]);
                    extra_sum += comp_contrib(r);
                }
            } else {
                int u = pr.i, v = pr.j;
                int ru = dsu.find(u), rv = dsu.find(v);
                if (ru != rv) {
                    extra_sum -= comp_contrib(ru) + comp_contrib(rv);
                    dsu.unite_roots(ru, rv);
                    int r = dsu.find(ru);
                    extra_sum += comp_contrib(r);
                }
            }
            pptr++;
        }
        ans[qi0] = sumB + extra_sum;
    }

    return ans;
}

• 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