Submission #1187383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187383		nikd	Nile (IOI24_nile)	C++20	100 / 100	81 ms	15932 KiB

nile

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

struct el{
    ll w, a, b;
};

struct nd{
    int sz;
    ll mnl, mnr, mn2;
    ll sm;
    ll sl;
};

nd f(nd a, nd b){
    a.mn2 = min(a.mn2, b.mn2);
    if(a.sz&1) swap(b.mnl, b.mnr);
    a.mnl = min(a.mnl, b.mnl);
    a.mnr = min(a.mnr, b.mnr);
    a.sz += b.sz;
    a.sm += b.sm;
    if(a.sz&1) a.sl = a.sm + min(a.mnl, a.mn2);
    else a.sl = a.sm;
    return a;
}

struct dsu{
    vector<int> p; vector<int> sz; vector<nd> vc;
    dsu(int n){
        p.resize(n);
        sz.resize(n, 1);
        for(int i= 0; i<n; i++) p[i] = i;
        vc.resize(n);
    }
    int find(int a){
        return p[a] == a ? a : p[a] = find(p[a]);
    }
    void merge(int a, int b){
        a = find(a); b = find(b);
        if(a==b) return;
        assert(a<b);
        nd n = f(vc[a], vc[b]);
        if(sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a]+=sz[b];
        vc[a] = n;
    }
};

std::vector<long long> calculate_costs( std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E){
    int n = W.size();
    vector<el> v(n);
    for(int i = 0; i<n; i++) v[i] = el{W[i], A[i], B[i]};
    sort(v.begin(), v.end(), [](el a, el b){return a.w<b.w;});
    vector<array<int, 2>> e(E.size());
    for(int i= 0; i<E.size(); i++) e[i] = {E[i], i};
    sort(e.begin(), e.end());
    vector<ll> sol(E.size(), 0);
    priority_queue<array<ll, 2>> pq;
    for(int i= 0; i<n-1; i++){
        pq.push({v[i].w-v[i+1].w, i});
    }
    priority_queue<array<ll, 2>> pq2;
    for(int i = 1; i<n-1; i++){
        pq2.push({v[i-1].w-v[i+1].w, i});
    }
    dsu ds(n);
    for(int i = 0; i<n; i++){
        ds.vc[i] = nd{1, v[i].a-v[i].b, LLONG_MAX, LLONG_MAX, v[i].b, v[i].a};
    }
    ll sl = 0;
    for(int i = 0; i<n; i++) sl += A[i];
    for(auto [d, j]: e){
        while(!pq.empty() && -pq.top()[0]<=d){
            int i = pq.top()[1];
            pq.pop();
            int a = ds.find(i);
            int b = ds.find(i+1);
            assert(a != b);
            sl -= ds.vc[a].sl + ds.vc[b].sl;
            ds.merge(a, b);
            a = ds.find(a);
            sl += ds.vc[a].sl;
        }
        while(!pq2.empty() && -pq2.top()[0] <= d){
            int i = pq2.top()[1];
            pq2.pop();
            int a = ds.find(i);
            ll olds = ds.vc[a].sl;
            ds.vc[a].mn2 = min( ds.vc[a].mn2, v[i].a-v[i].b);
            if(ds.vc[a].sz&1){
                ds.vc[a].sl = ds.vc[a].sm + min(ds.vc[a].mn2, ds.vc[a].mnl);
                sl += ds.vc[a].sl-olds;
            }
        }
        sol[j] = sl;
    }
    return sol;
/*    for(int j = 0; j<E.size(); j++){
        int d = E[j];
        int curr_l = 0;
        ll curr_mn = LLONG_MAX;
        ll sm = 0;
        for(int i= 0; i<n; i++){
            curr_l++;
            if(curr_l&1 || (i<n-1 && v[i+1].w-v[i-1].w <= d)) curr_mn = min(curr_mn, v[i].a-v[i].b);
            sm += v[i].b;
            if(i == n-1 || v[i+1].w-v[i].w > d){
                if(curr_l&1) sol[j] += sm+curr_mn;
                else sol[j] += sm;
                sm = 0;
                curr_l = 0;
                curr_mn = LLONG_MAX;
            }
        }
    }
    return sol;*/
}

• 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