Submission #1231032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231032		sahasrad	Nile (IOI24_nile)	C++20	38 / 100	84 ms	17092 KiB

nile

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

typedef long long ll;
typedef pair<int, int> pii;

struct DSU {
    int n;
    ll ans;
    vector<int> parent, size, mins;
    vector<ll> sum;

    DSU(int n, vector<vector<int>> arr) : n(n), ans(0), parent(n), size(n, 1), mins(n),sum(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            int a = arr[i][1], b = arr[i][2];
            mins[i] = a - b;
            ans += a;
            sum[i] = b;
        }
    }

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

    ll contrib(int x) {
        return sum[x] + (size[x] % 2) * mins[x];
    }

    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];
        mins[a] = min(mins[a], mins[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);
    for (int i = 0; i < n - 1; i++) {
        pq.push({i, arr[i + 1][0] - arr[i][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);
        }
        ans[j] = dsu.ans;
    }

    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