Submission #1244345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244345		riddles	Nile (IOI24_nile)	C++20	Compilation error	0 ms	0 KiB

nile

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

struct DSU {
    vector<int> parent, size;
    vector<int> even, odd;
    long long cost = 0;

    DSU(vector<int> &A, vector<int> &B) : parent(A.size(), -1), size(A.size(), 1), even(A.size()), odd(A.size(), INT_MAX) {
        for (int i = 0; i < A.size(); i++) {
            even[i] = A[i] - B[i];
            cost += even[i];
        }
    }
    int get_par(int x) {
        return ~parent[x] ? parent[x] = get_par(parent[x]) : x;
    }
    void merge(int v) {
        int u = get_par(v - 1);
        for (int x : {u, v})
            if (size[x] & 1)
                cost -= even[x];

        if (size[u] & 1)
            swap(even[v], odd[v]);
        odd[u] = min(odd[u], odd[v]);
        even[u] = min(even[u], even[v]);

        parent[v] = u;
        size[u] += size[v];
        if (size[u] & 1)
            cost += even[u];
    }
    void consider(int v, int w) {
        int u = get_par(v);
        if (v - u & 1) {
            if (size[u] & 1)
                cost -= even[u];
            even[u] = min(even[u], w);
            if (size[u] & 1)
                cost += even[u];
        }
        else
            odd[u] = min(odd[u], w);
    }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size(), q = E.size();
    if (n == 1)
        return vector<long long>(q, A[0]);

    vector<tuple<int, int, int>> helper;
    for (int i = 0; i < n; i++)
        helper.push_back({W[i], A[i], B[i]});
    sort(helper.begin(), helper.end());
    for (int i = 0; i < n; i++)
        tie(W[i], A[i], B[i]) = helper[i];

    vector<int> diff1(n - 1);
    iota(diff1.begin(), diff1.end(), 1);
    sort(diff1.begin(), diff1.end(), [&](int i, int j) {
        return W[i] - W[i - 1] < W[j] - W[j - 1];
    });

    vector<int> diff2(n - 2);
    iota(diff2.begin(), diff2.end(), 1);
    sort(diff2.begin(), diff2.end(), [&](int i, int j) {
        return W[i + 1] - W[i - 1] < W[j + 1] - W[j - 1];
    });

    vector<int> indexes(q);
    iota(indexes.begin(), indexes.end(), 0);
    sort(indexes.begin(), indexes.end(), [&](int i, int j) {
        return E[i] < E[j];
    });

    DSU dsu(A, B);
    int p1 = 0, p2 = 0;
    vector<long long> costs(q);
    long long total = accumulate(B.begin(), B.end(), 0LL);
    for (int index : indexes) {
        while (p1 < n - 1 && W[diff1[p1]] - W[diff1[p1] - 1] <= E[index]) {
            int idx = diff1[p1++];
            dsu.merge(idx);

            for (int p : {idx, idx - 1})
                if (p && p < n - 1 && W[p + 1] - W[p - 1] <= E[index] && dsu.get_par(p + 1) == dsu.get_par(p - 1))
                    dsu.consider(p, A[p] - B[p]);
        }
        while (p2 < n - 2 && W[diff2[p2] + 1] - W[diff2[p2] - 1] <= E[index]) {
            int idx = diff2[p2++];
            if (dsu.get_par(idx + 1) == dsu.get_par(idx - 1))
                dsu.consider(idx, A[idx] - B[idx]);
        }
        costs[index] = total + dsu.cost;
    }

    return costs;
}

Compilation message (stderr)

nile.cpp:2:10: fatal error: bits/stdc++/h: No such file or directory
    2 | #include <bits/stdc++/h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.