Submission #1126101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126101		joylintp	Nile (IOI24_nile)	C++20	38 / 100	82 ms	9560 KiB

nile

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

long long ans;
vector<int> DSU, cnt, oddMin, evenMin, avaMin;

int fnd(int a)
{
    if (a == DSU[a])
        return a;
    else
        return DSU[a] = fnd(DSU[a]);
}

void uni(int a)
{
    int b = a + 1;
    int x = fnd(a), y = fnd(b);
    if (x != y)
    {
        if (cnt[x] & 1)
            ans -= min(min(oddMin[x], evenMin[x]), avaMin[x]);
        if (cnt[y] & 1)
            ans -= min(min(oddMin[y], evenMin[y]), avaMin[y]);

        DSU[y] = DSU[x];
        cnt[x] += cnt[y];
        if (cnt[x] & 1)
        {
            oddMin[x] = min(oddMin[x], evenMin[y]);
            evenMin[x] = min(evenMin[x], oddMin[y]);
        }
        else
        {
            oddMin[x] = min(oddMin[x], oddMin[y]);
            evenMin[x] = min(evenMin[x], evenMin[y]);
        }
        avaMin[x] = min(avaMin[x], avaMin[y]);

        if (cnt[x] & 1)
            ans += min(min(oddMin[x], evenMin[x]), avaMin[x]);
    }
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
    int N = W.size();
    ans = 0;
    vector<pair<int, int>> art;
    for (int i = 0; i < N; i++)
    {
        art.push_back(make_pair(W[i], A[i] - B[i]));
        ans += A[i];
    }
    sort(art.begin(), art.end());

    DSU = cnt = oddMin = evenMin = avaMin = vector<int>(N);
    for (int i = 0; i < N; i++)
    {
        DSU[i] = i;
        cnt[i] = 1;
        oddMin[i] = art[i].second;
        evenMin[i] = avaMin[i] = INT_MAX;
    }

    vector<pair<int, int>> diff;
    for (int i = 0; i + 1 < N; i++)
        diff.push_back(make_pair(art[i + 1].first - art[i].first, i));
    sort(diff.begin(), diff.end(), greater<>());

    vector<pair<int, int>> margin;
    for (int i = 1; i + 1 < N; i++)
        margin.push_back(make_pair(art[i + 1].first - art[i - 1].first, i));
    sort(margin.begin(), margin.end(), greater<>());

    int Q = E.size();
    vector<pair<int, int>> queries;
    for (int i = 0; i < Q; i++)
        queries.push_back(make_pair(E[i], i));
    sort(queries.begin(), queries.end());

    vector<long long> R(Q);
    for (auto query : queries)
    {
        int D = query.first, queryIndex = query.second;

        while (!diff.empty() && diff.back().first <= D)
            uni(diff.back().second), diff.pop_back();
        while (!margin.empty() && margin.back().first <= D)
        {
            int target = margin.back().second;
            margin.pop_back();

            int root = fnd(target);
            if (cnt[root] & 1)
                ans -= min(min(oddMin[root], evenMin[root]), avaMin[root]);
            avaMin[root] = min(avaMin[root], art[target].second);
            if (cnt[root] & 1)
                ans += min(min(oddMin[root], evenMin[root]), avaMin[root]);
        }
        R[queryIndex] = ans;
    }
    return R;
}

• 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