Submission #1243447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243447		aykhn	Nile (IOI24_nile)	C++20	38 / 100	55 ms	8892 KiB

nile

#include "nile.h"
#include <vector>
#include <algorithm>
#include <limits>
#include <bits/stdc++.h>

using ll = long long;
using namespace std;
static const ll NEG_INF = std::numeric_limits<ll>::min() / 4;

// 2x2 max-plus matrix
struct Mat {
    ll a[2][2];
};

// Max-plus multiplication: C = B * A
static Mat mmul(const Mat &B, const Mat &A) {
    Mat C;
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            ll v = NEG_INF;
            for(int k = 0; k < 2; k++) {
                v = std::max(v, B.a[i][k] + A.a[k][j]);
            }
            C.a[i][j] = v;
        }
    }
    return C;
}

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(), Q = E.size();
    
    // base sum
    long long sumA = 0;
    for(int i = 0; i < N; i++) sumA += A[i];
    if(N == 1) return std::vector<ll>(Q, sumA);

    // sort items by weight
    struct It{int w, idx;};
    std::vector<It> it(N);
    for(int i=0;i<N;i++) it[i]={W[i],i};
    std::sort(it.begin(), it.end(),[](auto &x,auto &y){return x.w<y.w;});
    
    // compute gaps
    std::vector<pair<int,int>> gaps;
    for(int k=1;k<N;k++) gaps.emplace_back(it[k].w - it[k-1].w, k);
    std::sort(gaps.begin(), gaps.end());

    // queries sorted
    vector<pair<int,int>> qs(Q);
    for(int i=0;i<Q;i++) qs[i]={E[i],i};
    sort(qs.begin(), qs.end());
    
    // DSU
    vector<int> p(N), sz(N,1);
    vector<long long> sumd(N), mind(N);
    for(int i=0;i<N;i++){
        p[i]=i;
        sumd[i] = (long long)A[it[i].idx] - B[it[i].idx];
        mind[i] = sumd[i];
    }
    function<int(int)> find=[&](int x){return p[x]==x?x:p[x]=find(p[x]);};
    auto comp_val=[&](int r)->long long{
        // matched sum in component: if size even sumd, else sumd - mind
        if(sz[r]%2==0) return sumd[r];
        else return sumd[r] - mind[r];
    };
    long long matched=0;
    // initially no matches
    
    vector<long long> ans(Q);
    int ptr=0;
    for(auto &qr:qs){
        int D=qr.first, qi=qr.second;
        while(ptr<(int)gaps.size() && gaps[ptr].first<=D){
            int k=gaps[ptr].second;
            int u = find(k-1), v = find(k);
            if(u!=v){
                // remove old contributions
                matched -= comp_val(u);
                matched -= comp_val(v);
                // unify
                p[v]=u;
                sz[u]+=sz[v];
                sumd[u]+=sumd[v];
                mind[u]=min(mind[u], mind[v]);
                // add new
                matched += comp_val(u);
            }
            ptr++;
        }
        ans[qi] = sumA - matched;
    }
    return ans;
}

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