Submission #1231057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231057		sahasrad	Nile (IOI24_nile)	C++20	100 / 100	93 ms	19524 KiB

nile

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

typedef long long ll;
typedef pair<int, int> pii;
int inf = 1e9;

struct DSU {
    int n;
    ll ans;
    vector<int> parent, l, size, min1, min2, specialMin1, specialMin2;
    vector<ll> sum;

    DSU(int n, vector<vector<int>> arr) : n(n), ans(0), parent(n), l(n), size(n, 1),
                                          min1(n, inf), min2(n, inf),
                                          specialMin1(n, inf), specialMin2(n, inf),
                                          sum(n, 0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            int a = arr[i][1], b = arr[i][2];
            (i % 2 == 0 ? min1 : min2)[i] = a - b;
            l[i] = i;
            ans += a;
            sum[i] = b;
        }
    }

    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }

    ll contrib(int x) {
        bool even = l[x] % 2 == 0;
        return sum[x] + (size[x] % 2 == 1 ? min(even ? min1[x] : min2[x], even ? specialMin2[x] : specialMin1[x]) : 0);
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        ans -= contrib(a) + contrib(b);
        size[a] += size[b];
        sum[a] += sum[b];
        l[a] = min(l[a], l[b]);
        min1[a] = min(min1[a], min1[b]);
        min2[a] = min(min2[a], min2[b]);
        specialMin1[a] = min(specialMin1[a], specialMin1[b]);
        specialMin2[a] = min(specialMin2[a], specialMin2[b]);
        ans += contrib(a);
        return true;
    }
};

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<vector<int>> arr(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        arr[i][0] = W[i];
        arr[i][1] = A[i];
        arr[i][2] = B[i];
    }

    sort(arr.begin(), arr.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    auto comp = [](pii a, pii b) {
        return a.second > b.second;
    };

    priority_queue<pii, vector<pii>, decltype(comp)> pq(comp);
    priority_queue<pii, vector<pii>, decltype(comp)> pq2(comp);
    for (int i = 0; i < n - 1; i++) {
        pq.push({i, arr[i + 1][0] - arr[i][0]});
    }
    for (int i = 1; i < n - 1; i++) {
        pq2.push({i, arr[i + 1][0] - arr[i - 1][0]});
    }


    DSU dsu(n, arr);
    vector<pii> queries(q);
    for (int i = 0; i < q; i++) {
        queries[i] = {i, E[i]};
    }
    sort(queries.begin(), queries.end(), [](const pii& a, const pii& b) {
        return a.second < b.second;
    });

    vector<ll> ans(q);
    for (int qi = 0; qi < q; qi++) {
        auto [j, d] = queries[qi];
        while (!pq.empty() && pq.top().second <= d) {
            int i = pq.top().first;
            pq.pop();
            dsu.unite(i, i + 1);
        }
        while (!pq2.empty() && pq2.top().second <= d) {
            int i = pq2.top().first;
            pq2.pop();
            int rep = dsu.find(i);
            dsu.ans -= dsu.contrib(rep);
            vector<int>& specialMin = i % 2 == 0 ? dsu.specialMin1 : dsu.specialMin2;
            specialMin[rep] = min(specialMin[rep], arr[i][1] - arr[i][2]);
            dsu.ans += dsu.contrib(rep);
        }
        ans[j] = dsu.ans;
    }

    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