Submission #1302054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302054		regulardude6	Nile (IOI24_nile)	C++20	100 / 100	69 ms	13356 KiB

nile

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

using ll = long long;

struct DSU {
    int n;
    vector<int> p, sz, l;
    vector<ll> mn0, mn1, mn2;

    DSU(int n, const vector<ll>& C): n(n) {
        p.resize(n);
        sz.assign(n, 1);
        l.resize(n);
        mn0.resize(n);
        mn1.assign(n, (ll)4e18);
        mn2.assign(n, (ll)4e18);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            l[i] = i;
            mn0[i] = C[i];
        }
    }

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

    ll contrib(int r){
        if(sz[r] & 1) return min(mn0[r], mn2[r]);
        return 0;
    }

    void unite_adj(int a, int b, ll &extra){
        int ra = find(a), rb = find(b);
        if(ra == rb) return;
        if(l[ra] > l[rb]) swap(ra, rb);

        extra -= contrib(ra);
        extra -= contrib(rb);

        ll ne, no;
        if((sz[ra] & 1) == 0){
            ne = min(mn0[ra], mn0[rb]);
            no = min(mn1[ra], mn1[rb]);
        } else {
            ne = min(mn0[ra], mn1[rb]);
            no = min(mn1[ra], mn0[rb]);
        }
        ll nt = min(mn2[ra], mn2[rb]);

        p[rb] = ra;
        sz[ra] += sz[rb];
        mn0[ra] = ne;
        mn1[ra] = no;
        mn2[ra] = nt;

        extra += contrib(ra);
    }

    void enable_mid(int idx, ll val, ll &extra){
        int r = find(idx);
        ll old = contrib(r);
        mn2[r] = min(mn2[r], val);
        ll nw = contrib(r);
        extra += (nw - old);
    }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int N = (int)W.size();
    int Q = (int)E.size();

    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j){
        return W[i] < W[j];
    });

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

    struct Ev { ll d; int t; int i; };
    vector<Ev> ev;
    ev.reserve(2*N);
    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(), [&](const Ev& a, const Ev& b){
        if(a.d != b.d) return a.d < b.d;
        return a.t < b.t;
    });

    vector<int> qord(Q);
    iota(qord.begin(), qord.end(), 0);
    sort(qord.begin(), qord.end(), [&](int i, int j){
        return E[i] < E[j];
    });

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

    vector<ll> ans(Q);
    int p = 0;
    for(int qi : qord){
        int D = E[qi];
        while(p < (int)ev.size() && ev[p].d <= D){
            if(ev[p].t == 0){
                int i = ev[p].i;
                dsu.unite_adj(i, i+1, extra);
            } else {
                int i = ev[p].i;
                int mid = i + 1;
                dsu.enable_mid(mid, c[mid], extra);
            }
            p++;
        }
        ans[qi] = base + extra;
    }
    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