Submission #1295488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295488		lucas110550	Nile (IOI24_nile)	C++20	67 / 100	2094 ms	10616 KiB

nile

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<long long> tree;
    const long long NEG_INF = (long long)-4e18;  // sufficiently small

    SegTree(int size) {
        n = size;
        tree.assign(4 * n, NEG_INF);
    }

    void update(int idx, long long val, int node, int left, int right) {
        if (left == right) {
            if (val > tree[node]) tree[node] = val;
            return;
        }
        int mid = (left + right) / 2;
        if (idx <= mid) {
            update(idx, val, node * 2, left, mid);
        } else {
            update(idx, val, node * 2 + 1, mid + 1, right);
        }
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    void update(int idx, long long val) {
        update(idx, val, 1, 0, n - 1);
    }

    long long query(int ql, int qr, int node, int left, int right) {
        if (qr < left || ql > right) return NEG_INF;
        if (ql <= left && right <= qr) return tree[node];
        int mid = (left + right) / 2;
        long long left_val = NEG_INF, right_val = NEG_INF;
        if (ql <= mid) left_val = query(ql, qr, node * 2, left, mid);
        if (qr > mid)  right_val = query(ql, qr, node * 2 + 1, mid + 1, right);
        return max(left_val, right_val);
    }

    long long query(int ql, int qr) {
        if (ql > qr) return NEG_INF;
        return query(ql, qr, 1, 0, n - 1);
    }
};

vector<long long> calculate_costs(
    vector<int> W,
    vector<int> A,
    vector<int> B,
    vector<int> E
) {
    int n = (int)W.size();
    long long base = 0;
    for (long long x : A) base += x;

    if (n == 0) return {};

    // Build (W[i], s_val) array and sort by weight
    vector<pair<long long, long long>> arr;
    arr.reserve(n);
    for (int i = 0; i < n; ++i) {
        long long s_val = A[i] - B[i];
        arr.emplace_back(W[i], s_val);
    }

    sort(arr.begin(), arr.end(),
         [](const pair<long long,long long>& p1,
            const pair<long long,long long>& p2) {
             return p1.first < p2.first;
         });

    vector<long long> sorted_weights(n), sorted_s(n);
    for (int i = 0; i < n; ++i) {
        sorted_weights[i] = arr[i].first;
        sorted_s[i] = arr[i].second;
    }

    vector<long long> results;
    results.reserve(E.size());

    for (long long d : E) {
        vector<long long> dp(n + 1, 0);
        SegTree seg(n);

        for (int i = n - 1; i >= 0; --i) {
            long long bound = sorted_weights[i] + d;
            // upper_bound to mimic bisect_right
            int k = (int)(upper_bound(sorted_weights.begin(), sorted_weights.end(), bound)
                          - sorted_weights.begin()) - 1;

            if (i + 1 <= k) {
                long long max_val = seg.query(i + 1, k);
                long long candidate = sorted_s[i] + max_val;
                dp[i] = max(dp[i + 1], candidate);
            } else {
                dp[i] = dp[i + 1];
            }

            long long f_i = sorted_s[i] + dp[i + 1];
            seg.update(i, f_i);
        }

        long long total_saving = dp[0];
        long long cost = base - total_saving;
        results.push_back(cost);
    }

    return results;
}

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