Submission #1185970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185970		gyg	Nile (IOI24_nile)	C++20	32 / 100	69 ms	15604 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed 
#define int long long
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 1e5 + 5, INF = 1e18;

int n;
arr<pii, N> a;

vec<vec<int>> edg;
struct Dsj {
    arr<int, N> prnt, sz;
    void intl() {
        for (int u = 1; u <= n; u++)
            prnt[u] = u, sz[u] = 1;
    }
    int pr(int u) {
        return (u == prnt[u]) ? u : prnt[u] = pr(prnt[u]);
    }
    void mrg(int u, int v) {
        u = pr(u), v = pr(v);
        assert(u != v);
        prnt[v] = u, sz[u] += sz[v];
    }
    int evl(int u) {
        u = pr(u);
        return (sz[u] % 2 == 1) ? sz[u] - 1 : sz[u];
    }
} dsj;

vec<int> calculate_costs(vec<sig> _ps, vec<sig> _fl, vec<sig> _pr, vec<sig> _qr) {
    n = _ps.size();
    int whl = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = {_ps[i - 1], _fl[i - 1] - _pr[i - 1]};
        whl += _fl[i - 1];
    }
    sort(a.begin() + 1, a.begin() + n + 1);

    for (int i = 1; i <= n - 1; i++)
        edg.push_back({a[i + 1].fir - a[i].fir, i, i + 1});
    sort(edg.begin(), edg.end());
    dsj.intl();

    vec<pii> crt = {{0, 0}}; 
    int sm = 0;
    for (vec<int> x : edg) {
        int d = x[0], u = x[1], v = x[2];
        if (dsj.pr(u) == dsj.pr(v)) continue;
        sm -= dsj.evl(u), sm -= dsj.evl(v);
        dsj.mrg(u, v);
        sm += dsj.evl(u);
        crt.push_back({d, sm});
    }

    vec<int> ans;
    for (int d : _qr) {
        int lw = 0, hg = crt.size() - 1;
        while (lw < hg) {
            int md = (lw + hg + 1) / 2;
            if (d >= crt[md].fir) lw = md;
            else hg = md - 1;
        }
        ans.push_back(whl - crt[lw].sec);
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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