Submission #412694

#	Time	Username	Problem	Language	Result	Execution time	Memory
412694		KoD	Jousting tournament (IOI12_tournament)	C++17	100 / 100	123 ms	20028 KiB

tournament

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

struct FenwickTree {
    Vec<int> data;
    FenwickTree(const int n): data(n + 1) {}
    void add(int i, const int x) {
        i += 1;
        while (i < (int) data.size()) {
            data[i] += x;
            i += i & -i;
        }
    }
    int get(int i) const {
        int ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }
    int fold(const int l, const int r) const {
        return get(r) - get(l);
    }
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    if (R == N - 1) return 0;
    FenwickTree fen(N);
    const auto get_kth = [&](const int k) {
        int ok = -1, ng = N;
        while (ng - ok > 1) {
            const auto md = (ok + ng) / 2;
            (fen.fold(0, md) <= k ? ok : ng) = md;
        }
        return ok;
    };
    const int V = N + C;
    Vec<int> max(V, -1);
    Vec<int> belong(N);
    for (int i = 0; i < N; ++i) {
        fen.add(i, 1);
        belong[i] = i;
    }
    std::array<Vec<int>, 20> par;
    par[0] = Vec<int>(V);
    for (int i = 0; i < C; ++i) {
        const int u = N + i;
        for (int j = S[i]; j <= E[i]; ++j) {
            const auto k = get_kth(S[i]);
            const auto v = belong[k];
            par[0][v] = u;
            max[u] = std::max(max[u], max[v]);
            if (j == E[i]) {
                belong[k] = u;
            }
            else {
                max[u] = std::max(max[u], K[k]);
                fen.add(k, -1);
            }
        }
    }
    par[0][N + C - 1] = N + C - 1;
    for (int i = 1; i < 20; ++i) {
        par[i] = Vec<int>(V);
        for (int j = 0; j < V; ++j) {
            par[i][j] = par[i - 1][par[i - 1][j]];
        }
    }
    int ret = -1, val = -1;
    for (int i = 0; i < N; ++i) {
        int len = 0;
        int u = i;
        for (int j = 19; j >= 0; --j) {
            const auto v = par[j][u];
            if (max[v] < R) {
                u = v;
                len += 1 << j;
            }
        }
        if (val < len) {
            val = len;
            ret = i;
        }
    }
    return ret;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51