B. Tryouts

**Definitions** Let $ n, m, d \in \mathbb{Z} $, with $ 2 \leq n \leq 10^5 $, $ 1 \leq m \leq 10^9 $, $ 1 \leq d \leq 10^5 $. Let $ A = (a_1, a_2, \dots, a_n) $ be the initial sequence of distances tortoises can run, where $ 1 \leq a_i < m $. Let $ k \in \mathbb{Z}^+ $ be the number of tortoises cursed per second (fixed but unspecified in input; assumed given per race). Let $ Q = \{(r_j, l_j, r_j, u_j, v_j) \mid j \in \{1, \dots, d\}\} $ be the sequence of operations, where: - If $ r_j = 1 $: race query on interval $[l_j, r_j]$ - If $ r_j = 2 $: update $ a_{u_j} \leftarrow v_j $ **Constraints** 1. For all $ i \in \{1, \dots, n\} $, $ 1 \leq a_i < m $ 2. For update operations ($ r_j = 2 $): $ 1 \leq u_j \leq n $, $ 1 \leq v_j < m $ 3. For race queries ($ r_j = 1 $): $ 1 \leq l_j \leq r_j \leq n $ **Objective** For each race query $ j $ with interval $[l_j, r_j]$: Let $ B = (a_{l_j}, a_{l_j+1}, \dots, a_{r_j}) $, and define $ d_i = m - a_i $ for each $ i \in [l_j, r_j] $, the remaining distance to finish. Let $ D = \{d_i \mid i \in [l_j, r_j]\} $. At each second, the hare curses the $ k $ tortoises with the **smallest remaining distances** (i.e., closest to finish), freezing them for 1 second. All others advance 1 meter. The hare sleeps until **all remaining distances are ≤ 1**, and **at least one tortoise has remaining distance exactly 1** and **there are more than $ k $ such tortoises** — then he must wake up. Find the maximum number of seconds $ t $ the hare can sleep before being forced to wake up. Formally, simulate the process: - Let $ R = \{d_i\} $ (multiset of remaining distances). - While $ \max(R) > 1 $: - Let $ C $ be the multiset of the $ \min(k, |R|) $ smallest elements in $ R $. - Remove $ C $ from $ R $. - Decrement all elements in $ R \setminus C $ by 1. - Add back $ C $ unchanged. - Increment $ t $. - Return $ t $. Alternatively, compute $ t $ as the minimal number of seconds such that after $ t $ seconds of the above process, the number of tortoises with remaining distance $ \leq 1 $ is $ |R| $, and the number with remaining distance $ =1 $ is $ > k $. **Note**: Since direct simulation is too slow, compute $ t $ via binary search on time or by sorting and greedy counting. **Final Formal Objective**: For each race query $[l, r]$, compute the minimal $ t \in \mathbb{N} $ such that, after $ t $ seconds of the described process, $$ \left| \left\{ i \in [l, r] \mid m - a_i - \max(0, t - c_i) \leq 1 \right\} \right| = r - l + 1 $$ and $$ \left| \left\{ i \in [l, r] \mid m - a_i - \max(0, t - c_i) = 1 \right\} \right| > k $$ where $ c_i $ is the number of times tortoise $ i $ was cursed in $ t $ seconds (determined by greedy selection of smallest remaining distances). But since $ c_i $ depends on $ t $ and the dynamic process, the cleanest formal output is: $$ \boxed{t = \min \left\{ s \in \mathbb{N} \ \middle| \ \text{after } s \text{ seconds of the described curse-and-advance process, } \#\{i : d_i^{(s)} = 1\} > k \right\}} $$ where $ d_i^{(s)} $ is the remaining distance of tortoise $ i $ after $ s $ seconds.