Submission #1277282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277282		BlockOG	Nile (IOI24_nile)	C++20	38 / 100	81 ms	13836 KiB

nile

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

int dsu[100000];
int dsv[100000];
int siz[100000];

long long sum = 0;

int get(int i) {
    if (dsu[i] == i) return i;
    return dsu[i] = get(dsu[i]);
}

void merge(int i, int j) {
    i = get(i), j = get(j);
    if (i == j) return;
    if (siz[i] < siz[j]) swap(i, j);

    if (siz[i] % 2 == 1) sum -= dsv[i];
    if (siz[j] % 2 == 1) sum -= dsv[j];
    dsv[i] = min(dsv[i], dsv[j]);
    siz[i] += siz[j];
    if (siz[i] % 2 == 1) sum += dsv[i];
    dsu[j] = i;
}

vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
    int n = w.size(), q = e.size();

    vector<pair<int, int>> c(n);
    fo(i, 0, n) sum += a[i], c[i] = {w[i], a[i] - b[i]};
    sort(be(c));

    map<int, vector<int>> ds;
    fo(i, 0, q) ds[e[i]].pb(i);
    vector<long long> res(q);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dsu[0] = 0, dsv[0] = c[0].s, siz[0] = 1;
    fo(i, 1, n) dsu[i] = i, dsv[i] = c[i].s, siz[i] = 1, pq.push({c[i].f - c[i - 1].f, i});

    for (auto [d, is] : ds) {
        while (pq.size() && pq.top().f <= d) {
            auto [diff, i] = pq.top();
            pq.pop();
            merge(i, i - 1);
        }

        for (int i : is) res[i] = sum;
    }

    return res;
}

• 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