Submission #1186661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186661		gyg	Nile (IOI24_nile)	C++20	6 / 100	2096 ms	26340 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;
    arr<int, N> lf, rg, ex;
    void intl() {
        for (int u = 1; u <= n; u++)
            prnt[u] = lf[u] = rg[u] = u, ex[u] = 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], ex[u] = min(ex[u], ex[v]);
    }
    void upd(int u) {
        ex[pr(u)] = min(ex[pr(u)], 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({a[lf[u]].sec, a[rg[u]].sec, ex[u]});
        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});

    auto cmp = [](vec<int> &x, vec<int> &y) {
        if (x[0] < y[0]) return true;
        return (x.size() > y.size());        
    };
    sort(ev.begin(), ev.end(), cmp);

    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: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18