Submission #1307026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307026		succe_ed	Nile (IOI24_nile)	C++20	0 / 100	129 ms	34908 KiB

nile

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

using namespace std;

const long long INF = 1e18;

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

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

Matrix merge(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                // Combine ranges such that the total number of items 
                // used across the boundary maintains the correct offset.
                C.m[i][j] = min(C.m[i][j], A.m[i][k] + B.m[k][j]);
            }
        }
    }
    return C;
}

int SZ;
Matrix tree[400005];
bool can_pair2[100005], can_pair3[100005];
Artifact sorted_arts[100005];

void update_node(int v, int idx) {
    tree[v] = Matrix();
    // Case 1: Send artifact alone (Cost A)
    tree[v].m[0][1] = sorted_arts[idx].a;
    tree[v].m[1][2] = sorted_arts[idx].a;
    tree[v].m[2][0] = sorted_arts[idx].a;

    // Case 2: Send in a pair (Cost B)
    // Offset logic handles the parity of pairs
    if (can_pair2[idx]) {
        tree[v].m[0][2] = min(tree[v].m[0][2], (long long)sorted_arts[idx].b + sorted_arts[idx - 1].b);
        tree[v].m[1][0] = min(tree[v].m[1][0], (long long)sorted_arts[idx].b + sorted_arts[idx - 1].b);
        tree[v].m[2][1] = min(tree[v].m[2][1], (long long)sorted_arts[idx].b + sorted_arts[idx - 1].b);
    }
    
    // Case 3: Skip one (triple range)
    if (can_pair3[idx]) {
        tree[v].m[0][0] = min(tree[v].m[0][0], (long long)sorted_arts[idx].b + sorted_arts[idx - 2].b + sorted_arts[idx - 1].a);
        tree[v].m[1][1] = min(tree[v].m[1][1], (long long)sorted_arts[idx].b + sorted_arts[idx - 2].b + sorted_arts[idx - 1].a);
        tree[v].m[2][2] = min(tree[v].m[2][2], (long long)sorted_arts[idx].b + sorted_arts[idx - 2].b + sorted_arts[idx - 1].a);
    }
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        update_node(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_node(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();
    vector<pair<int, int>> temp(n);
    for (int i = 0; i < n; i++) temp[i] = {W[i], i};
    sort(temp.begin(), temp.end());

    for (int i = 0; i < n; i++) {
        sorted_arts[i] = {W[temp[i].second], A[temp[i].second], B[temp[i].second]};
    }

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

    int q = E.size();
    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 ptr = 0;
    for (int i = 0; i < q; i++) {
        while (ptr < edges.size() && edges[ptr].first <= queries[i].first) {
            int val = edges[ptr].second;
            if (val < n) {
                can_pair2[val] = true;
                update(1, 0, n - 1, val);
            } else {
                can_pair3[val - n] = true;
                update(1, 0, n - 1, val - n);
            }
            ptr++;
        }
        results[queries[i].second] = tree[1].m[0][n % 3];
    }

    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