Submission #1128303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128303		TrendBattles	Jousting tournament (IOI12_tournament)	C++17	100 / 100	139 ms	32920 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;


const int inf_32 = 0x3f3f3f3f;

struct FenwickTree {
    vector <int> node;
    int N;
    FenwickTree(int N): N(N), node(N) {
        for (int i = 0; i < N; ++i) {
            node[i] = (i + 1) & -(i + 1);
        }
    }

    int find_value_by_order(int s) {
        int p = -1;
        for (int i = __lg(N); i >= 0; --i) {
            if (p + (1 << i) >= N) continue;

            if (node[p + (1 << i)] < s) {
                p += 1 << i;
                s -= node[p];
            }
        }

        p += 1;
        return p;
    }

    void update(int u, int v) {
        for (; u < N; u |= u + 1) {
            node[u] += v;
        }
    }

    int ask(int u) {
        int ans = 0;
        for (; u >= 0; u = (u & (u + 1)) - 1) {
            ans += node[u];
        }
        return ans;
    }

    int ask_range(int l, int r) {
        return ask(r) - ask(l - 1);
    }

    void reset() {
        node.assign(N, 0);
    }
};

int GetBestPosition(int N, int M, int R, int *K, int *S, int *E) {
    vector <int> value(N);
    value[0] = R;
    for (int i = 0; i + 1 < N; ++i) {
        value[i + 1] = K[i];
    }

    vector <int> temp_ID(N);
    iota(temp_ID.begin(), temp_ID.end(), 0);
    
    vector <vector <int>> graph(N + M);
    FenwickTree tree(N + M);

    for (int i = 0; i < M; ++i) {
        S[i] += 1; E[i] += 1;
        
        vector <int> vertex_id(E[i] - S[i] + 1);

        for (int j = 0; j < (int) vertex_id.size(); ++j) {
            int pos = tree.find_value_by_order(j + S[i]);
            vertex_id[j] = temp_ID[pos];

            graph[i + N].push_back(vertex_id[j]);
        }

        temp_ID[tree.find_value_by_order(S[i])] = i + N;

        for (int j = (int) vertex_id.size() - 1; j; --j) {
            tree.update(tree.find_value_by_order(j + S[i]), -1);
        }
    }

    const int root = N + M - 1;
    vector <int> time_in(N + M), time_out(N + M), depth(N + M);

    vector <vector <int>> anc(__lg(N + M) + 1, vector <int> (N + M));
    int timeDFS = -1;

    auto DFS = [&] (auto DFS, int u) -> void {
        time_in[u] = ++timeDFS;
        for (int v : graph[u]) {
            depth[v] = depth[u] + 1;
            anc[0][v] = u;

            DFS(DFS, v);
        }
        time_out[u] = timeDFS;
    };
    DFS(DFS, root);

    tree.reset();

    vector <int> state(N);
    for (int i = 0; i < N; ++i) {
        state[i] = value[0] < value[i];
        tree.update(time_in[i], +state[i]);
    }


    for (int i = 1; i <= __lg(N + M); ++i) {
        for (int u = 0; u < N + M; ++u) {
            anc[i][u] = anc[i - 1][anc[i - 1][u]];
        }
    }

    pair <int, int> optimal_ans{-inf_32, -1};

    for (int u = 0; u < N; ++u) {
        int x = u;
        
        for (int i = __lg(depth[u]); i >= 0; --i) {
            if (depth[x] < (1 << i)) continue;

            int nxt_x = anc[i][x];
            if (tree.ask_range(time_in[nxt_x], time_out[nxt_x]) == 0) {
                x = nxt_x;
            }
        }

        optimal_ans = max(optimal_ans, make_pair(depth[u] - depth[x], -u));

        if (u + 1 < N) {
            tree.update(time_in[u], -state[u]);
            tree.update(time_in[u + 1], -state[u + 1]);

            swap(state[u], state[u + 1]);
            
            tree.update(time_in[u], +state[u]);
            tree.update(time_in[u + 1], +state[u + 1]);
        }
    }

    optimal_ans.second = -optimal_ans.second;

    return optimal_ans.second;
}

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