Overview

When players retire in order of increasing stamina value, determine each player’s rank (position from the left) immediately before they retire.

Analysis

In this problem, players are lined up in a row at their initial positions, and they retire in order of increasing stamina value. When a player retires, they leave the row, and the remaining players shift to fill the gap (left-justified).

A naive approach of actually deleting from and compacting a list each time a player retires would result in \(O(N^2)\) time complexity, which is too slow for the constraint \(N \leq 2 \times 10^5\).

The key observation is that “each player’s initial position is fixed, and only the order of retirement is determined by stamina values.” In other words, a player’s rank equals their initial position minus “the number of players to their left who have already retired.”

With this insight, instead of actually manipulating a list, we can record the positions of retired players and use binary search to efficiently compute the answer.

Algorithm

1. Record each player’s initial position. This corresponds to the input index, and we prepare a reverse lookup from stamina values to player positions.
2. Process in order of stamina value \(k = 1, 2, \ldots, N\).
3. For each \(k\), retrieve the initial position of the player with stamina value \(k\).
4. Using a sorted list removed_positions that tracks the positions of players who have already retired, perform a binary search to find how many players before the current player’s initial position have already retired.
5. Subtract that count to obtain the current player’s rank among remaining players (1-based).
6. Finally, insert the current player’s position into removed_positions (maintaining sorted order).

Complexity

• Time complexity: \(O(N \log N)\)
  Each player requires one binary search and one insertion operation, both of which are \(O(\log N)\).
• Space complexity: \(O(N)\)
  Linear memory is used for pos, removed_positions, result, etc.

Implementation Notes

• Use bisect_left to efficiently find the insertion position in the sorted list.

• Use insort to insert elements while maintaining sorted order.

• It is important to pre-build the pos array so that we can reverse-lookup the correspondence between player numbers and stamina values.

  Source Code

import sys
from bisect import bisect_left, insort

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    L = list(map(int, data[1:N+1]))
    
    # 選手の初期位置（1-indexed）を記録
    pos = [0] * (N + 1)  # pos[i] := 選手 i の初期位置（1-based）
    for i in range(N):
        pos[L[i]] = i + 1
    
    # リタイアした選手の位置を管理するリスト（ソートされた状態を維持）
    removed_positions = []
    result = [0] * N  # 結果を格納する配列（0-indexed）

    # スタミナ値 k = 1 から N まで処理
    for k in range(1, N + 1):
        current_pos = pos[k]  # スタミナ値 k の選手の初期位置
        # removed_positions の中で current_pos 未満の要素の個数を求める
        idx = bisect_left(removed_positions, current_pos)
        # 残っている選手中での位置 = 初期位置 - 自分より左にリタイアした人数
        rank = current_pos - idx
        result[k - 1] = rank
        # リタイアした位置を追加
        insort(removed_positions, current_pos)
    
    # 結果を出力
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.