Submission #1243442

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

nile

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

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

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

// multiply B * A in max-plus semiring
static Matrix mul(const Matrix &B, const Matrix &A) {
    Matrix 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();
    int Q = E.size();
    std::vector<ll> result(Q, 0);
    // sum of sending alone costs
    ll sumA = 0;
    for(int i = 0; i < N; i++) sumA += A[i];
    if(N == 1) {
        // only one artifact: always alone
        for(int j = 0; j < Q; j++) result[j] = sumA;
        return result;
    }
    // sort artifacts by weight
    struct Item { int w; ll delta; };
    std::vector<Item> items(N);
    for(int i = 0; i < N; i++) {
        items[i].w = W[i];
        items[i].delta = (ll)A[i] - (ll)B[i];
    }
    std::sort(items.begin(), items.end(), [](auto &x, auto &y){ return x.w < y.w; });
    // compute gaps
    std::vector<std::pair<int,int>> gaps;
    gaps.reserve(N-1);
    for(int i = 0; i < N-1; i++) {
        int g = items[i+1].w - items[i].w;
        gaps.emplace_back(g, i+1); // edge index = i+1
    }
    std::sort(gaps.begin(), gaps.end(), [](auto &x, auto &y){ return x.first < y.first; });
    // prepare queries
    std::vector<std::pair<int,int>> queries(Q);
    for(int j = 0; j < Q; j++) queries[j] = {E[j], j};
    std::sort(queries.begin(), queries.end());
    // segment tree over edges 1..N-1, size = next pow2 of N
    int sz = 1;
    while(sz < N) sz <<= 1;
    std::vector<Matrix> seg(2*sz);
    // identity matrix
    Matrix 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
    Matrix Off;
    Off.a[0][0] = NEG_INF; Off.a[0][1] = 0;
    Off.a[1][0] = NEG_INF; Off.a[1][1] = 0;
    // initialize leaves
    for(int i = 0; i < sz; i++) {
        if(i >= 1 && i < N) seg[sz + i] = Off;
        else seg[sz + i] = I;
    }
    // build
    for(int i = sz-1; i >= 1; i--) {
        seg[i] = mul(seg[2*i+1], seg[2*i]);
    }
    // sweep gaps and queries
    int ptr = 0;
    for(auto &q : queries) {
        int D = q.first, qid = q.second;
        // activate all gaps with g <= D
        while(ptr < (int)gaps.size() && gaps[ptr].first <= D) {
            int k = gaps[ptr].second; // edge index
            // build On matrix for this k
            Matrix On;
            On.a[0][0] = NEG_INF; On.a[0][1] = 0;
            ll wsum = items[k].delta + items[k-1].delta;
            On.a[1][0] = wsum; On.a[1][1] = 0;
            // update leaf at pos k
            int pos = sz + k;
            seg[pos] = On;
            // rebuild up
            pos >>= 1;
            while(pos >= 1) {
                seg[pos] = mul(seg[2*pos+1], seg[2*pos]);
                pos >>= 1;
            }
            ptr++;
        }
        // root stores product of all M; initial state [0,0]
        // matched sum = max(root.a[1][0]+0, root.a[1][1]+0)
        ll matched = std::max(seg[1].a[1][0], seg[1].a[1][1]);
        result[qid] = sumA - matched;
    }
    return result;
}

• 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