Submission #1302053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302053		regulardude6	나일강 (IOI24_nile)	C++20	38 / 100	62 ms	13224 KiB

nile

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

using ll = long long;

struct DSU {
    vector<int> p, sz, mn;
    vector<ll> evenv, oddv, twov;

    DSU(int n, vector<ll>& C) {
        p.resize(n);
        sz.assign(n, 1);
        mn.resize(n);
        evenv.resize(n);
        oddv.assign(n, LLONG_MAX);
        twov.assign(n, LLONG_MAX);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            mn[i] = i;
            evenv[i] = C[i];
        }
    }

    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }

    ll cost(int x) {
        if (sz[x] & 1) return min(evenv[x], twov[x]);
        return 0;
    }

    void merge(int a, int b, ll &cur) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (mn[a] > mn[b]) swap(a, b);
        cur -= cost(a);
        cur -= cost(b);
        ll ne = min(evenv[a], (sz[a] & 1) ? oddv[b] : evenv[b]);
        ll no = min(oddv[a], (sz[a] & 1) ? evenv[b] : oddv[b]);
        ll nt = min(twov[a], twov[b]);
        p[b] = a;
        sz[a] += sz[b];
        evenv[a] = ne;
        oddv[a] = no;
        twov[a] = nt;
        cur += cost(a);
    }

    void enable(int x, vector<ll>& C, ll &cur) {
        x = find(x);
        if (sz[x] & 1) {
            ll old = min(evenv[x], twov[x]);
            twov[x] = min(twov[x], C[mn[x] + 1]);
            ll nw = min(evenv[x], twov[x]);
            cur += nw - old;
        } else {
            twov[x] = min(twov[x], C[mn[x] + 1]);
        }
    }
};

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<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int a, int b){ return W[a] < W[b]; });

    vector<ll> w(n), c(n);
    ll base = 0;
    for (int i = 0; i < n; i++) {
        w[i] = W[id[i]];
        c[i] = (ll)A[id[i]] - B[id[i]];
        base += B[id[i]];
    }

    struct Edge { ll d; int t, i; };
    vector<Edge> ev;
    for (int i = 0; i + 1 < n; i++) ev.push_back({w[i+1] - w[i], 0, i});
    for (int i = 0; i + 2 < n; i++) ev.push_back({w[i+2] - w[i], 1, i});
    sort(ev.begin(), ev.end(), [](auto &a, auto &b){ return a.d < b.d; });

    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b){ return E[a] < E[b]; });

    DSU dsu(n, c);
    ll cur = 0;
    for (int i = 0; i < n; i++) cur += c[i];

    vector<ll> ans(q);
    int p = 0;
    for (int qi : ord) {
        while (p < (int)ev.size() && ev[p].d <= E[qi]) {
            if (ev[p].t == 0) dsu.merge(ev[p].i, ev[p].i + 1, cur);
            else dsu.enable(ev[p].i, c, cur);
            p++;
        }
        ans[qi] = base + cur;
    }
    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