Submission #1208829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208829		sula2	Nile (IOI24_nile)	C++20	67 / 100	2089 ms	8744 KiB

nile

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;

struct segtree {
    vector<long long> tree;
    int offset = 1;

    segtree(int n) {
        while (offset < n) offset <<= 1;
        tree.resize(offset << 1);
    }

    void update(int i, long long x) {
        tree[i += offset] = x;
        while (i >>= 1) tree[i] = min(tree[i*2], tree[i*2 + 1]);
    }

    long long query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (qr < l || r < ql) return 1e18;
        int mid = l+r >> 1;
        return min(query(2*v, l, mid, ql, qr),
            query(2*v+1, mid+1, r, ql, qr));
    }

    long long query(int l, int r) { return query(1, 0, offset - 1, l, r); }
};

long long solve(vector<int> W, vector<int> A,
                vector<int> B, int D) {
    int n = W.size();
    vector<int> ind(n);
    iota(all(ind), 0);
    sort(all(ind), [&](int i, int j) { return W[i] < W[j]; });
    vector<long long> dp(n);
    segtree s(n);
    dp[0] = A[ind[0]];
    long long sum = A[ind[0]];
    int j = 0;
    s.update(0, -A[ind[0]] + B[ind[0]]);
    for (int i = 1; i < n; i++) {
        while (W[ind[i]] - W[ind[j]] > D)
            j++;
        dp[i] = dp[i-1] + A[ind[i]];
        if (j < i) {
            dp[i] = min(dp[i], sum + s.query(j, i-1) + B[ind[i]]);
        }
        sum += A[ind[i]];
        s.update(i, -sum + dp[i-1] + B[ind[i]]);
    }
    return dp[n-1];
}

vector<long long> calculate_costs(
        vector<int> W, vector<int> A,
        vector<int> B, vector<int> E
        ) {
    int n = W.size(), q = E.size();
    vector<long long> res(q);
    for (int i = 0; i < q; i++) {
        res[i] = solve(W, A, B, E[i]);
    }
    return res;
}

• 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