IOI 2012 - Jousting Tournament

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

struct Fenwick {
    int n;
    vector<int> bit;

    explicit Fenwick(int n_) : n(n_), bit(n_ + 1, 0) {}

    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    int kth(int k) const {
        int idx = 0;
        int step = 1;
        while ((step << 1) <= n) step <<= 1;
        for (; step > 0; step >>= 1) {
            int next = idx + step;
            if (next <= n && bit[next] < k) {
                idx = next;
                k -= bit[next];
            }
        }
        return idx + 1;
    }
};

struct Node {
    int l = 0;
    int r = 0;
    int parent = -1;
    vector<int> children;
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    vector<Node> nodes(N + C);
    for (int i = 0; i < N; ++i) {
        nodes[i].l = nodes[i].r = i;
    }

    Fenwick fw(N);
    vector<int> slot_node(N), nxt(N, -1), prv(N, -1);
    for (int i = 0; i < N; ++i) {
        fw.add(i + 1, 1);
        slot_node[i] = i;
        if (i > 0) prv[i] = i - 1;
        if (i + 1 < N) nxt[i] = i + 1;
    }

    int node_cnt = N;
    for (int round = 0; round < C; ++round) {
        int left_slot = fw.kth(S[round] + 1) - 1;
        int right_slot = fw.kth(E[round] + 1) - 1;

        int cur = left_slot;
        vector<int> children;
        while (true) {
            children.push_back(slot_node[cur]);
            if (cur == right_slot) break;
            cur = nxt[cur];
        }

        int id = node_cnt++;
        nodes[id].children = children;
        nodes[id].l = nodes[children.front()].l;
        nodes[id].r = nodes[children.back()].r;
        for (int child : children) nodes[child].parent = id;

        slot_node[left_slot] = id;
        int after = nxt[right_slot];
        cur = nxt[left_slot];
        while (cur != after) {
            fw.add(cur + 1, -1);
            int next_cur = nxt[cur];
            prv[cur] = nxt[cur] = -1;
            cur = next_cur;
        }
        nxt[left_slot] = after;
        if (after != -1) prv[after] = left_slot;
    }

    int root_slot = fw.kth(1) - 1;
    int root = slot_node[root_slot];

    vector<int> strong_prefix(N, 0);
    for (int i = 0; i < N - 1; ++i) {
        strong_prefix[i + 1] = strong_prefix[i] + (K[i] > R);
    }
    strong_prefix[N - 1] = strong_prefix[N - 1];

    auto good = [&](int id) -> bool {
        return strong_prefix[nodes[id].r] - strong_prefix[nodes[id].l] == 0;
    };

    vector<int> chain(node_cnt, 0), answer(N, 0);
    vector<int> st = {root};
    chain[root] = good(root) ? 1 : 0;
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        for (int child : nodes[u].children) {
            if (child < N) {
                answer[child] = chain[u];
            } else {
                chain[child] = good(child) ? chain[u] + 1 : 0;
                st.push_back(child);
            }
        }
    }

    int best_pos = 0;
    for (int i = 1; i < N; ++i) {
        if (answer[i] > answer[best_pos]) best_pos = i;
    }
    return best_pos;
}

int main() {
    int N, C, R;
    if (!(cin >> N >> C >> R)) return 0;
    vector<int> K(max(0, N - 1)), S(C), E(C);
    for (int i = 0; i < N - 1; ++i) cin >> K[i];
    for (int i = 0; i < C; ++i) cin >> S[i] >> E[i];
    cout << GetBestPosition(N, C, R, K.data(), S.data(), E.data()) << '\n';
    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{listings}
\usepackage{xcolor}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{gray},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2012 -- Jousting Tournament}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
There are $N$ final positions, one of which will be occupied by the late knight of rank $R$.
The other $N-1$ positions contain the ranks in array $K$ in their original order.
For each round $i$, the master removes the consecutive range of current positions
$[S_i, E_i]$, keeps only the strongest knight in that range, and packs the remaining
knights to the left.
We must choose the insertion position of the late knight so that the number of rounds he
personally wins is maximized.

\section{Key Observation}
The sequence of rounds defines an ordered tree on the \emph{final} $N$ positions:
each leaf is one initial position, and each round creates one internal node whose children
are the consecutive survivors currently inside the announced interval.
This tree depends only on $(S_i, E_i)$, not on the ranks.

Consider an internal node whose leaf interval is $[l, r]$.
If the late knight is inserted anywhere inside this interval, then the other knights
participating in that node are exactly the original knights
$K_l, K_{l+1}, \dots, K_{r-1}$.
Hence the late knight wins this round if and only if
\[
\max(K_l, K_{l+1}, \dots, K_{r-1}) < R.
\]
So every internal node is either:
\begin{itemize}
  \item \textbf{good}: every original knight in $K_l \dots K_{r-1}$ is weaker than $R$;
  \item \textbf{bad}: otherwise.
\end{itemize}
For a leaf position $p$, the number of rounds won by the late knight is exactly the number
of consecutive good ancestors of leaf $p$.

\section{Building the Tree}
We maintain the current survivors as a linked list of active slots and a Fenwick tree over
the slots. For round $[S,E]$:
\begin{enumerate}
  \item Use the Fenwick tree to find the active slots currently at positions $S$ and $E$.
  \item Traverse that linked-list segment; those nodes become the children of a new internal node.
  \item Replace the whole segment by the new node at its leftmost slot, and deactivate the
        remaining slots.
\end{enumerate}
Each node becomes a child exactly once, so the total linked-list traversal is linear.
The Fenwick operations contribute the $\log N$ factor.

\section{Checking Good Nodes}
Define
\[
\text{strongPrefix}[i] = \#\{\,0 \le j < i : K_j > R\,\}.
\]
Then an internal node with leaf interval $[l,r]$ is good iff
\[
\text{strongPrefix}[r] - \text{strongPrefix}[l] = 0.
\]
After building the tournament tree, we do one DFS from the root.
If an internal node is good, its ``good-chain length'' is
\[
1 + \text{good-chain(parent)};
\]
otherwise it is $0$.
For each leaf, the answer is the good-chain length of its parent.

\section{Complexity}
\begin{itemize}
  \item \textbf{Time:} $O(N \log N)$.
  \item \textbf{Space:} $O(N)$.
\end{itemize}

\section{Implementation}
\begin{lstlisting}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    // 1. Build the tournament tree from the rounds.
    // 2. Mark each internal node as good/bad using the prefix count of ranks > R.
    // 3. DFS once to compute the good-chain length of every node.
    // 4. For each leaf position, the answer is the chain length of its parent.
}
\end{lstlisting}

\end{document}