Submission #1160259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160259		JahonaliX	Nile (IOI24_nile)	C++20	100 / 100	120 ms	21188 KiB

nile

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct dsu {
    int n;
    vector<int> p, l;
    vector<ll> t, j, f;
    ll x = 0;
    dsu(vector<ll> &a) {
        n = a.size();
        p.assign(n, 0);
        l.assign(n, 1);
        t = a;
        x = accumulate(a.begin(), a.end(), 0ll);
        j.assign(n, INT_MAX);
        f.assign(n, INT_MAX);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        if (x == p[x]) return x;
        return p[x] = find(p[x]);
    }
    void merge(int a, int b) {
        if (a > b) swap(a, b);
        a = find(a);
        b = find(b);
        x -= l[a] % 2 * min(t[a], f[a]);
        x -= l[b] % 2 * min(t[b], f[b]);
        if (l[a] % 2) t[a] = min(t[a], j[b]), j[a] = min(j[a], t[b]);
        else t[a] = min(t[a], t[b]), j[a] = min(j[a], j[b]);
        f[a] = min(f[a], f[b]);
        p[b] = a;
        l[a] += l[b];
        x += l[a] % 2 * min(t[a], f[a]);
    }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    vector<long long> ans;
    int q = (int) E.size(), n = (int) W.size();
    for (int i = 0; i < n; ++i) A[i] -= B[i];
    vector<int> o(n);
    iota(o.begin(), o.end(), 0);
    sort(o.begin(), o.end(), [&](int i, int j) { return W[i] < W[j]; });
    vector<ll> w(n), a(n), b(n);
    for (int i = 0; i < n; ++i) w[i] = W[o[i]], a[i] = A[o[i]], b[i] = B[o[i]];    
    set<pair<int, int>> s;
    set<tuple<ll, ll, ll>> c;
    for (int i = 1; i < n; ++i) s.emplace(w[i] - w[i - 1], i);
    for (int i = 2; i < n; ++i) c.emplace(w[i] - w[i - 2], a[i - 1], i - 1);
    o.assign(q, 0);
    iota(o.begin(), o.end(), 0);
    sort(o.begin(), o.end(), [&](int i, int j) { return E[i] < E[j]; });
    dsu d(a);
    ans.assign(q, 0);
    ll wth = 0;
    for (int i : b) wth += i;
    for (int i = 0; i < q; ++i) {
        int e = E[o[i]];
        while (s.size() && (*s.begin()).first <= e) {
            int x = (*s.begin()).second;
            d.merge(x, x - 1);
            s.erase(s.begin());
        } 
        while (c.size() && get<0>(*c.begin()) <= e) {
            auto [x, y, z] = *c.begin();
            c.erase(c.begin());
            z = d.find(z);
            d.x -= d.l[z] % 2 * min(d.t[z], d.f[z]);
            d.f[z] = min(d.f[z], y);
            d.x += d.l[z] % 2 * min(d.t[z], d.f[z]);
        }
        ans[o[i]] = d.x + wth;
    }
    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