Submission #1279195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279195		BlockOG	Nile (IOI24_nile)	C++20	100 / 100	119 ms	17356 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;
}();

struct DSV {
    int mi;
    int even, odd;
    int two;
};

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

long long sum = 0;

int sum_diff(int i) {
    return siz[i] % 2 == 1 ? min(dsv[i].mi % 2 == 0 ? dsv[i].even : dsv[i].odd, dsv[i].two) : 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);

    sum -= sum_diff(i);
    sum -= sum_diff(j);

    dsv[i].mi = min(dsv[i].mi, dsv[j].mi);
    dsv[i].even = min(dsv[i].even, dsv[j].even);
    dsv[i].odd = min(dsv[i].odd, dsv[j].odd);
    dsv[i].two = min(dsv[i].two, dsv[j].two);
    siz[i] += siz[j];
    dsu[j] = i;

    sum += sum_diff(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, pair<int, bool>>, vector<pair<int, pair<int, bool>>>, greater<pair<int, pair<int, bool>>>> pq;
    fo(i, 0, n) dsu[i] = i, dsv[i].mi = i, dsv[i].even = i % 2 == 0 ? c[i].s : INT_MAX, dsv[i].odd = i % 2 == 1 ? c[i].s : INT_MAX,
                dsv[i].two = INT_MAX, siz[i] = 1;
    fo(i, 1, n) pq.push({c[i].f - c[i - 1].f, {i, false}});
    fo(i, 2, n) pq.push({c[i].f - c[i - 2].f, {i - 1, true}});

    for (auto [d, is] : ds) {
        while (pq.size() && pq.top().f <= d) {
            auto [diff, v] = pq.top();
            auto [i, t] = v;
            pq.pop();
            if (t) {
                int new_two = c[i].s;
                i = get(i);
                sum -= sum_diff(i);
                dsv[i].two = min(dsv[i].two, new_two);
                sum += sum_diff(i);
            } else merge(i, i - 1);
        }

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

    return res;
}

• 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