Submission #1243444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243444		aykhn	Nile (IOI24_nile)	C++20	32 / 100	78 ms	15432 KiB

nile

#include "nile.h"
#include <vector>
#include <algorithm>

using ll = long long;
static const ll NEG_INF = -(1LL<<60);

// 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++) {
                ll x = B.a[i][k] + A.a[k][j];
                if(x > v) v = x;
            }
            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 = (int)W.size();
    int Q = (int)E.size();
    
    // base sum if all alone
    ll sumA = 0;
    for(int i = 0; i < N; i++) sumA += A[i];
    
    // handle trivial N=1
    if(N == 1) {
        std::vector<ll> R(Q, sumA);
        return R;
    }
    
    // build items sorted by weight
    struct Item { int w; ll d; };
    std::vector<Item> it(N);
    for(int i = 0; i < N; i++) {
        it[i].w = W[i];
        it[i].d = (ll)A[i] - (ll)B[i];
    }
    std::sort(it.begin(), it.end(), [](auto &L, auto &R){ return L.w < R.w; });
    
    // compute gaps (gap, index)
    // index k means between it[k-1] and it[k]
    std::vector<std::pair<int,int>> gaps;
    gaps.reserve(N-1);
    for(int k = 1; k < N; k++) {
        gaps.emplace_back(it[k].w - it[k-1].w, k);
    }
    std::sort(gaps.begin(), gaps.end());
    
    // sort queries (D, original idx)
    std::vector<std::pair<int,int>> qs(Q);
    for(int j = 0; j < Q; j++) qs[j] = {E[j], j};
    std::sort(qs.begin(), qs.end());
    
    // build seg-tree size = next pow2 >= N
    int SZ = 1;
    while(SZ < N) SZ <<= 1;
    std::vector<Mat> seg(2*SZ);
    
    // identity matrix in max-plus
    Mat I;
    I.a[0][0] = 0;      I.a[0][1] = NEG_INF;
    I.a[1][0] = NEG_INF;I.a[1][1] = 0;
    // off-edge matrix
    Mat Off;
    Off.a[0][0] = NEG_INF; Off.a[0][1] = 0;
    Off.a[1][0] = NEG_INF; Off.a[1][1] = 0;
    
    // init leaves
    for(int i = 0; i < SZ; i++) {
        if(i >= 1 && i < N) seg[SZ + i] = Off;
        else seg[SZ + i] = I;
    }
    // build internals
    for(int i = SZ-1; i >= 1; i--) {
        seg[i] = mmul(seg[2*i+1], seg[2*i]);
    }
    
    std::vector<ll> R(Q);
    int ptr = 0;
    // process queries
    for(auto &qq : qs) {
        int D = qq.first;
        int qi = qq.second;
        // activate gaps with gap <= D
        while(ptr < (int)gaps.size() && gaps[ptr].first <= D) {
            int k = gaps[ptr].second;
            // on-edge matrix at k
            Mat On = Off;
            ll sumd = it[k].d + it[k-1].d;
            On.a[1][0] = sumd;
            // update leaf k
            int pos = SZ + k;
            seg[pos] = On;
            pos >>= 1;
            while(pos) {
                seg[pos] = mmul(seg[2*pos+1], seg[2*pos]);
                pos >>= 1;
            }
            ptr++;
        }
        // seg[1] holds full product; matched = max(dp[N-1], dp[N]) = max(a[1][0], a[1][1])
        Mat &M = seg[1];
        ll matched = M.a[1][0] > M.a[1][1] ? M.a[1][0] : M.a[1][1];
        R[qi] = sumA - matched;
    }
    return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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