Submission #1241010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241010		kargneq	Nile (IOI24_nile)	C++20	32 / 100	195 ms	38752 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pii = array<int,3>;

static const int MAXN = 100000, MAXT = 270000;
struct Mat {
    lint A[3][3];
    Mat() {
        const lint INF = LLONG_MAX/3;
        for(int i=0;i<3;i++) for(int j=0;j<3;j++)
            A[i][j] = (i==j ? 0 : INF);
    }
    // min-plus matrix multiplication
    Mat operator+(const Mat &m) const {
        Mat r;
        const lint INF = LLONG_MAX/3;
        for(int i=0;i<3;i++) for(int j=0;j<3;j++)
            r.A[i][j] = INF;
        for(int i=0;i<3;i++) for(int k=0;k<3;k++)
            for(int j=0;j<3;j++)
                r.A[i][k] = min(r.A[i][k], A[i][j] + m.A[j][k]);
        return r;
    }
} M[MAXN];

struct SegTree {
    int n, lim;
    vector<Mat> st;
    void init(int _n) {
        n = _n;
        lim = 1; while(lim < n) lim <<= 1;
        st.assign(2*lim, Mat());
        for(int i=0;i<n;i++) st[lim+i] = M[i];
        for(int i=lim-1;i>0;i--) st[i] = st[2*i] + st[2*i+1];
    }
    void update(int p, const Mat &v) {
        p += lim;
        st[p] = v;
        for(p>>=1; p; p>>=1)
            st[p] = st[2*p] + st[2*p+1];
    }
    // root matrix = st[1]
};

vector<long long> calculate_costs(
    vector<int> W, vector<int> A,
    vector<int> B, vector<int> E
) {
    int n = W.size();
    vector<array<int,3>> a(n);
    for(int i=0;i<n;i++)
        a[i] = {W[i], A[i], B[i]};
    sort(a.begin(), a.end());  // sort by weight

    // Prepare events: (gap, left_index, right_index)
    vector<array<int,3>> events;
    for(int i=1;i<n;i++){
        events.push_back({a[i][0]-a[i-1][0], i-1, i});
        if(i>1)
            events.push_back({a[i][0]-a[i-2][0], i-2, i});
    }
    sort(events.begin(), events.end(),
         [](auto &x, auto &y){ return x[0]<y[0]; });

    // Initialize leaf matrices
    for(int i=0;i<n;i++){
        // reset to INF-diagonal then set M[i].A[0][0]=A[i]
        Mat m; const lint INF = LLONG_MAX/3;
        for(int u=0;u<3;u++) for(int v=0;v<3;v++)
            m.A[u][v] = INF;
        m.A[0][0] = a[i][1];
        m.A[1][0] = 0;
        m.A[2][1] = 0;
        M[i] = m;
    }

    SegTree seg; seg.init(n);

    // Sweep D from 0 upward, recording (D, cost)
    vector<pair<int, lint>> record;
    record.emplace_back(0, seg.st[1].A[0][0]);
    for(auto &ev : events){
        int gap = ev[0], L = ev[1], R = ev[2];
        Mat m = M[L];
        // if R=L+1: pairing L and R
        if(R == L+1){
            m.A[0][1] = a[L][2] + a[R][2];
        } else {
            // triple grouping L, L+1, R
            m.A[0][2] = a[L][2] + a[R][2] + a[L+1][1];
        }
        seg.update(L, m);
        M[L] = m;
        record.emplace_back(gap, seg.st[1].A[0][0]);
    }

    // Answer queries by binary searching record
    vector<long long> ans(E.size());
    vector<pair<int,int>> qs(E.size());
    for(int i=0;i<(int)E.size();i++) qs[i] = {E[i], i};
    sort(qs.begin(), qs.end());
    int idx = 0;
    for(auto &q : qs){
        while(idx+1 < (int)record.size() && record[idx+1].first <= q.first)
            idx++;
        ans[q.second] = record[idx].second;
    }
    return ans;
}

• 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