Submission #1102034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102034		woohyun_jng	Nile (IOI24_nile)	C++17	100 / 100	117 ms	24644 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#define int long long

#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;
typedef pair<int, int> pr;
typedef array<int, 3> tp;

vector<int> parent, res, odd[2], even[2], sz, sum;

int find(int K) {
    if (parent[K] != K)
        parent[K] = find(parent[K]);
    return parent[K];
}

int calc(int X) {
    X = find(X);
    if (sz[X] & 1)
        res[X] = sum[X] + min(odd[1][X], even[0][X]);
    else
        res[X] = sum[X];
    return res[X];
}

int merge(int X, int Y) {
    X = find(X), Y = find(Y);
    int ret = -res[X] - res[Y];

    if (X > Y)
        swap(X, Y);

    if (sz[X] & 1) {
        odd[0][X] = min(odd[0][X], even[0][Y]);
        even[0][X] = min(even[0][X], odd[0][Y]);
        odd[1][X] = min(odd[1][X], even[1][Y]);
        even[1][X] = min(even[1][X], odd[1][Y]);
    } else {
        odd[0][X] = min(odd[0][X], odd[0][Y]);
        even[0][X] = min(even[0][X], even[0][Y]);
        odd[1][X] = min(odd[1][X], odd[1][Y]);
        even[1][X] = min(even[1][X], even[1][Y]);
    }

    sum[X] = sum[X] + sum[Y];
    parent[Y] = X;
    sz[X] += sz[Y];

    res[X] = calc(X);
    ret += res[X];

    return ret;
}

vector<int> calculate_costs(vector<signed> W, vector<signed> A,
                            vector<signed> B, vector<signed> E) {
    int Q = E.size(), N = W.size(), D, cur = 0, X, Y;
    vector<pr> queries, one, two;
    vector<tp> arr(N);

    parent.resize(N + 1), res.resize(N + 1), sz.resize(N + 1), sum.resize(N + 1);
    for (int i = 0; i < 2; i++)
        odd[i].resize(N + 1), even[i].resize(N + 1);

    for (int i = 0; i < N; i++)
        arr[i] = {W[i], A[i] - B[i], B[i]};
    sort(arr.begin(), arr.end());

    for (int i = 0; i < N; i++) {
        parent[i] = i;
        sz[i] = 1;

        res[i] = arr[i][1] + arr[i][2];
        cur += res[i];
        sum[i] = arr[i][2];

        odd[1][i] = arr[i][1];
        odd[0][i] = even[0][i] = even[1][i] = INF;
    }

    vector<int> R(Q, 0);

    for (int i = 1; i < N; i++)
        one.push_back({arr[i][0] - arr[i - 1][0], i});
    for (int i = 2; i < N; i++)
        two.push_back({arr[i][0] - arr[i - 2][0], i});
    sort(one.begin(), one.end(), greater<pr>());
    sort(two.begin(), two.end(), greater<pr>());

    for (int i = 0; i < Q; i++)
        queries.push_back({E[i], i});
    sort(queries.begin(), queries.end());

    for (pr i : queries) {
        D = i.first;

        while (!one.empty() && one.back().first <= D) {
            X = one.back().second, one.pop_back();
            cur += merge(X - 1, X);
        }

        while (!two.empty() && two.back().first <= D) {
            X = two.back().second - 1, two.pop_back();
            Y = find(X);
            cur -= res[Y];

            if ((X - Y) & 1)
                even[0][Y] = min(even[0][Y], arr[X][1]);
            else
                odd[0][Y] = min(odd[0][Y], arr[X][1]);

            cur += calc(Y);
        }

        R[i.second] = cur;
    }

    return R;
}

• 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: 15 / 15
• Subtask 7: 18 / 18