제출 #1186667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186667		gyg	나일강 (IOI24_nile)	C++20	100 / 100	114 ms	29584 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;

arr<int, N> sm;
vec<vec<int>> ev;
struct Dsj {
    arr<int, N> prnt, lf, rg;
    arr<arr<int, 2>, N> mn, ex;
    void intl() {
        for (int u = 1; u <= n; u++) {
            prnt[u] = lf[u] = rg[u] = u;
            mn[u][u % 2] = a[u].sec, mn[u][!(u % 2)] = INF;
            ex[u][0] = ex[u][1] = INF;
        }
    } 
    int pr(int u) {
        return (prnt[u] == u) ? u : prnt[u] = pr(prnt[u]);
    }
    void mrg(int u, int v) {
        u = pr(u), v = pr(v);
        assert(u != v);
        assert(rg[u] == lf[v] - 1);
        prnt[v] = u, rg[u] = rg[v];
        for (int i : {0, 1}) {
            mn[u][i] = min(mn[u][i], mn[v][i]);
            ex[u][i] = min(ex[u][i], ex[v][i]);
        }
    }
    void upd(int u) {
        ex[pr(u)][u % 2] = min(ex[pr(u)][u % 2], a[u].sec);
    }
    int evl(int u) {
        u = pr(u);
        int ans = sm[rg[u]] - sm[lf[u] - 1];
        int sz = rg[u] - lf[u] + 1;
        if (sz % 2 == 1) ans -= min({mn[u][lf[u] % 2], ex[u][!(lf[u] % 2)]});
        return ans;
    }
} dsj;
void prp_cmp() {
    for (int i = 1; i <= n; i++)
        sm[i] = sm[i - 1] + a[i].sec;

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

    // for (vec<int> x : ev) {
    //     for (int y : x) cout << y << " ";
    //     cout << '\n';
    // }

    dsj.intl();
}

vec<pii> crt;
void crt_cmp() {
    crt.push_back({0, 0});
    int ans = 0;
    for (vec<int> x : ev) {
        if (x.size() == 3) {
            int d = x[0], u = x[1], v = x[2];
            ans -= dsj.evl(u), ans -= dsj.evl(v);
            dsj.mrg(u, v);
            ans += dsj.evl(u);
            crt.push_back({d, ans});
        } else {
            int d = x[0], u = x[1];
            ans -= dsj.evl(u);
            dsj.upd(u);
            ans += dsj.evl(u);
            crt.push_back({d, ans});
        }
    }
}

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);

    prp_cmp();
    crt_cmp();

    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: 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