Submission #1233081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233081		shiocan	Nile (IOI24_nile)	C++20	45 / 100	74 ms	15164 KiB

nile

#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
#define ull unsigned long long 
#define ld long double
#define ll long long
// #define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7; 
const ll inf = 1e18;
const int N = 1e5 + 50, K = 22;

// #include "nile.h"

ll n;
ll sum = 0;
vector<ll> c;
vector<pair<ll, ll>> q;

struct dsu{
    vector<ll> sz, p, minodd, mineven, minidx, altmin;
    ll tot = 0;

    dsu(int n){
        sz = p = minodd = mineven = minidx = altmin = vector<ll> (n + 5, 0ll);
        for(int i = 0; i < n; i++){
            sz[i] = 1, p[i] = i, minidx[i] = i, tot += c[i];
            
            minodd[i] = mineven[i] = altmin[i] = inf;
            if(i % 2)
                minodd[i] = c[i];
            else
                mineven[i] = c[i];
        }
    }

    ll find(ll u){
        return p[u] == u ? u : p[u] = find(p[u]);
    }

    ll cost(ll u){
        u = find(u);
        if(sz[u] % 2 == 0)
            return 0;
        if(minidx[u] % 2)
            return min(minodd[u], altmin[u]);
        return min(mineven[u], altmin[u]);
    }

    bool merge(int a, int b){
        int idx = min(a, b) + 1;
        a = find(a);
        b = find(b);

        if(a == b){
            tot -= cost(a);
            altmin[a] = min(altmin[a], c[idx]);
            tot += cost(a);
            return false;
        }
        
        if(sz[a] < sz[b])
            swap(a, b); 
    
        tot -= cost(a);
        tot -= cost(b);

        minodd[a] = min(minodd[a], minodd[b]);
        mineven[a] = min(mineven[a], mineven[b]);
        minidx[a] = min(minidx[a], minidx[b]);
        altmin[a] = min(altmin[a], altmin[b]);
        sz[a] += sz[b];
        p[b] = a;

        tot += cost(a);

        return true;
    }
};

struct item{
    ll w, a, b;
};
    
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e){
    n = a.size();
    c = vector<ll> (n, 0ll);
    vector<ll> ans((ll)e.size());

    for(auto i : b)
        sum += i;

    vector<item> arr(n);
    for(int i = 0; i < n; i++)  
        arr[i] = {w[i], a[i], b[i]};
    
    sort(all(arr), [](item x, item y){
        return x.w < y.w;
    });

    for(int i = 0; i < n; i++)
        c[i] = arr[i].a - arr[i].b;

    for(int i = 0; i < e.size(); i++)
        q.push_back({e[i], i});

    sort(all(q));
    
    vector<pii> p;
    for(int i = 0; i < n - 1; i++){
        p.push_back({i, i + 1});
        if(i + 2 < n)
            p.push_back({i, i + 2});
    }

    sort(all(p), [&](pii x, pii y){
        return arr[x.second].w - arr[x.first].w < arr[y.second].w - arr[y.first].w;        
    });

    dsu ds(n);

    int i = 0;
    for(auto [d, idx] : q){
        while(i < p.size() && arr[p[i].second].w - arr[p[i].first].w <= d){
            ds.merge(p[i].first, p[i].second);
            i++;
        }

        ans[idx] = sum + ds.tot;
    }   

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18