Submission #1317257

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

nile

using ll = long long;

const int MAXN = 100000;
int pred[MAXN];
int sz[MAXN];
int min_c[MAXN];
ll cur_add = 0;

int get(int v) {
    if (v == pred[v]) return v;
    return pred[v] = get(pred[v]);
}

void unite(int v, int u) {
    v = get(v);
    u = get(u);
    if (sz[v] > sz[u]) std::swap(v, u);
    if (sz[v] & 1) cur_add -= min_c[v];
    if (sz[u] & 1) cur_add -= min_c[u];

    pred[v] = u;
    sz[u] += sz[v];
    min_c[u] = std::min(min_c[u], min_c[v]);

    if (sz[u] & 1) cur_add += min_c[u];
}

std::vector <ll> calculate_costs(std::vector <int> W, std::vector <int> A, std::vector <int> B, std::vector <int> E) {
    struct event {
        int t; // 0 - update, 1 - get
        int ind;
        int d;

        event(int t, int ind, int d): t(t), ind(ind), d(d) {}

        bool operator<(const event &oth) const {
            return std::tie(d, t) < std::tie(oth.d, oth.t);
        }
    };

    int n = A.size();

    std::fill(sz, sz + n, 1);
    std::iota(pred, pred + n, 0);

    std::vector <event> es;
    for (int i = 0; i < E.size(); ++i) {
        es.push_back(event(1, i, E[i]));
    }

    int p[n];
    std::iota(p, p + n, 0);
    std::sort(p, p + n, [&](int i, int j) {
        return W[i] < W[j];
    });

    for (int i = 1; i < n; ++i) {
        es.push_back(event(0, i - 1, abs(W[p[i]] - W[p[i - 1]])));
    }

    std::vector <int> C(n);
    for (int i = 0; i < n; ++i) C[i] = A[i] - B[i];
    for (int i = 0; i < n; ++i) min_c[i] = C[p[i]];
    for (int i = 0; i < n; ++i) cur_add += C[p[i]];

    ll sm = 0;
    for (int i = 0; i < n; ++i) {
        sm += B[i];
    }
    sort(es.begin(), es.end());

    std::vector <ll> ans(E.size());
    for (event e : es) {
        if (e.t == 0) {
            unite(e.ind, e.ind + 1);
        } else if (e.t == 1) {
            ans[e.ind] = sm + cur_add;
        }
    }

    return ans;
}

Compilation message (stderr)

nile.cpp: In function 'void unite(int, int)':
nile.cpp:17:29: error: 'swap' is not a member of 'std'
   17 |     if (sz[v] > sz[u]) std::swap(v, u);
      |                             ^~~~
nile.cpp:23:21: error: 'min' is not a member of 'std'
   23 |     min_c[u] = std::min(min_c[u], min_c[v]);
      |                     ^~~
nile.cpp: At global scope:
nile.cpp:28:6: error: 'vector' in namespace 'std' does not name a template type
   28 | std::vector <ll> calculate_costs(std::vector <int> W, std::vector <int> A, std::vector <int> B, std::vector <int> E) {
      |      ^~~~~~
nile.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | using ll = long long;