Editorial

Let $p_r$ be the nearest position left of $r$ with height greater than $A_r$ , or $0$ if none exists. Dadas wins under exactly these conditions:

If $A_l<A_r$ , some internal height exceeds $A_l$ .

Process right endpoints $r$ from left to right. A Fenwick tree stores earlier heights; let $F(v)$ count those at most $v$ . Maintain a stack of indices with decreasing heights. Pop all heights below $A_r$ , recording their number . The remaining top, if any, is .

Combining both types, the contribution of $r$ is

F(h_r-1)-c_r,\qquad h_r=\begin{cases}A_{p_r}&p_r>0,\\A_r&p_r=0.\end{cases}

Add it to the answer, insert $A_r$ into the Fenwick tree, and push $r$ onto the stack. Time complexity is $O(N\log N)$ and space complexity is $O(N)$ .

Proof

If $A_l<A_r$ , Dadas can move to the rightmost internal position higher than $A_l$ . Every remaining internal height is below , so Ttas cannot move. If no such position exists, Dadas cannot move.

Mountain Climbing Game

Editorial