oj.uz

Submission #412694

# Submission time Handle Problem Language Result Execution time Memory
412694 2021-05-27T11:05:40 Z KoD Jousting tournament (IOI12_tournament) C++17
100 / 100
 123 ms 20028 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 5 ms 1228 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 5 ms 1200 KB Output is correct
5 Correct 5 ms 1072 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 5 ms 1228 KB Output is correct
8 Correct 5 ms 1228 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 6 ms 1208 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8388 KB Output is correct
2 Correct 123 ms 20028 KB Output is correct
3 Correct 57 ms 10788 KB Output is correct
4 Correct 111 ms 19908 KB Output is correct
5 Correct 112 ms 19388 KB Output is correct
6 Correct 98 ms 16500 KB Output is correct
7 Correct 113 ms 19996 KB Output is correct
8 Correct 112 ms 19928 KB Output is correct
9 Correct 53 ms 10252 KB Output is correct
10 Correct 59 ms 10692 KB Output is correct