Overview

This problem asks us to determine each player’s position from the left just before they retire, as players retire in order of increasing stamina values.

Analysis

A naive approach would be to actually delete elements from an array at each retirement and recalculate positions. However, deleting an element from an array and shifting elements takes \(O(N)\) time, resulting in \(O(N^2)\) total time, which is too slow when \(N\) can be up to \(2 \times 10^5\).

For an efficient solution, the following observations are key: - The retirement order is fixed as the ascending order of stamina values - To find a player’s position before retiring, we can take their initial position and subtract the number of previously retired players who were to their left - We can use a data structure to efficiently handle element deletions and order queries

Algorithm

We use a SortedList (a type of balanced binary search tree). Initially, we store all players’ initial positions (1-indexed) in the list.

1. Record the initial position of the player with stamina value \(k\) in the array pos_map
2. Add all initial positions (1 through N) to the SortedList
3. Process in order of increasing stamina values (k = 1 to N):
   • Retrieve the current player’s initial position
   • Use binary search on the SortedList to count the number of elements less than or equal to that position (this gives the current position from the left)
   • Remove that player’s position from the SortedList

This allows each step to handle deletion and queries in \(O(\log N)\) time.

Complexity

• Time complexity: \(O(N \log N)\)
  • Each SortedList operation (insertion, deletion, binary search) takes \(O(\log N)\) time
  • This is repeated N times
• Space complexity: \(O(N)\)
  • Memory for the SortedList and auxiliary arrays

Implementation Details

• Use pos_map to create a mapping from stamina values to initial positions

• Use bisect_left on the SortedList to count the number of elements less than or equal to the current position

• Element deletion is performed using the remove method

• Since the output corresponds to stamina values 1 through N in order, record results in an array ans and output them sequentially

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    L = list(map(int, data[1:1+n]))
    
    pos_map = [0] * (n + 1)
    for idx, stamina in enumerate(L):
        pos_map[stamina] = idx + 1
        
    ans = [0] * (n + 1)
    from sortedcontainers import SortedList
    sl = SortedList(range(1, n + 1))
    
    for k in range(1, n + 1):
        pos = pos_map[k]
        idx_in_sl = sl.bisect_left(pos)
        ans[k] = idx_in_sl + 1
        sl.remove(pos)
        
    for k in range(1, n + 1):
        print(ans[k])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.