Submission #1307025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307025		succe_ed	Nile (IOI24_nile)	C++20	0 / 100	214 ms	37276 KiB

nile

#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e16;

struct Matrix {
    long long mat[3][3];
    Matrix() {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                mat[i][j] = -INF;
    }
};

struct Artifact {
    int w, a, b;
    long long p;
};

struct Edge {
    int diff, type, idx;
    bool operator<(const Edge& other) const {
        return diff < other.diff;
    }
};

int NN;
Matrix tree[400005];
bool act2[100005], act3[100005];
long long profits[100005];

Matrix merge(const Matrix& a, const Matrix& b) {
    Matrix res;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                for (int l = 0; l + k <= 2; l++) {
                    res.mat[i][j] = max(res.mat[i][j], a.mat[i][k] + b.mat[l][j]);
                }
            }
        }
    }
    return res;
}

void update_leaf(int v, int i) {
    tree[v] = Matrix();
    tree[v].mat[0][0] = 0;
    if (act2[i]) tree[v].mat[1][1] = profits[i] + profits[i - 1];
    if (act3[i]) tree[v].mat[2][2] = profits[i] + profits[i - 2];
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        update_leaf(v, tl);
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
    }
}

void update(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        update_leaf(v, tl);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2 * v, tl, tm, pos);
        else update(2 * v + 1, tm + 1, tr, pos);
        tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
    }
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size();
    int q = E.size();
    NN = n;
    vector<Artifact> arts(n);
    long long total_a = 0;
    for (int i = 0; i < n; i++) {
        arts[i] = {W[i], A[i], B[i], (long long)A[i] - B[i]};
        total_a += A[i];
    }
    sort(arts.begin(), arts.end(), [](const Artifact& x, const Artifact& y) {
        return x.w < y.w;
    });

    for (int i = 0; i < n; i++) profits[i] = arts[i].p;

    vector<Edge> edges;
    for (int i = 1; i < n; i++) edges.push_back({arts[i].w - arts[i - 1].w, 2, i});
    for (int i = 2; i < n; i++) edges.push_back({arts[i].w - arts[i - 2].w, 3, i});
    sort(edges.begin(), edges.end());

    vector<pair<int, int>> queries(q);
    for (int i = 0; i < q; i++) queries[i] = {E[i], i};
    sort(queries.begin(), queries.end());

    build(1, 0, n - 1);

    vector<long long> results(q);
    int edge_ptr = 0;
    for (int i = 0; i < q; i++) {
        while (edge_ptr < edges.size() && edges[edge_ptr].diff <= queries[i].first) {
            if (edges[edge_ptr].type == 2) act2[edges[edge_ptr].idx] = true;
            else act3[edges[edge_ptr].idx] = true;
            update(1, 0, n - 1, edges[edge_ptr].idx);
            edge_ptr++;
        }
        
        long long max_profit = -INF;
        for (int r = 0; r < 3; r++) max_profit = max(max_profit, tree[1].mat[0][r]);
        results[queries[i].second] = total_a - max_profit;
    }

    return results;
}

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