Overview

Given the scores \(P_i\) of \(N\) students, the problem asks to find the attendance number of the student who achieved the highest score among those whose scores fall within a specified range \([L, R]\).

Analysis

To solve this problem, we need to find a student who satisfies all three of the following conditions:

1. The score \(P_i\) satisfies \(L \le P_i \le R\).
2. Among the students satisfying condition 1, the score \(P_i\) is the maximum.
3. If there are multiple students satisfying condition 2, the attendance number \(i\) is the smallest.

Checking the constraints, the number of students \(N\) is at most \(2 \times 10^5\). By performing a “linear search” that checks each student’s score one by one, we only need a total of \(N\) comparisons, which is well within the time limit.

To efficiently handle the condition “maximum score, and smallest attendance number in case of ties,” the key is to iterate through students from the beginning and only record the attendance number when the current student’s score strictly exceeds the highest score seen so far among qualifying students.

Algorithm

We find the solution using the following steps:

1. Initialize “current maximum score (max_score)” to -1 and “the corresponding attendance number (ans_id)” to -1.
2. For each student from \(i = 1\) to \(N\), check their score \(P_i\) in order:
   • If \(L \le P_i \le R\) and \(P_i > \text{max\_score}\):
     • Update max_score to \(P_i\).
     • Update ans_id to the current attendance number \(i\).
3. After checking all students, output ans_id.

Complexity

• Time complexity: \(O(N)\)
  • Since we check each of the \(N\) students’ scores exactly once, the computation finishes in time proportional to the number of students.
• Space complexity: \(O(N)\)
  • If we store all scores in a list, we use memory proportional to the input size. (It is also possible to reduce this to \(O(1)\) by reading input incrementally.)

Implementation Notes

• Update condition: By using score > max_score without including equality (updating only when strictly greater), when scores are tied, the “first found (= smallest attendance number) student” is preferentially retained.

• Initial values: Since we need to output -1 when there are no qualifying students, setting the initial value of ans_id to -1 allows us to output it directly without adding extra conditional branches, which is clean.

• Fast I/O: In Python, when the data size is large (around \(2 \times 10^5\)), using sys.stdin.read().split() or similar to read all input at once can reduce execution time.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N, L, R を取得
    N = int(input_data[0])
    L = int(input_data[1])
    R = int(input_data[2])
    
    # 生徒の得点リストを取得
    # P_i は input_data[3] から input_data[3 + N - 1] まで
    scores = input_data[3:]
    
    max_score = -1
    ans_id = -1
    
    # 各生徒の得点を順番に確認
    for i in range(N):
        score = int(scores[i])
        
        # 合格範囲内（L以上R以下）か判定
        if L <= score <= R:
            # 現在の最大得点よりも高い場合のみ更新
            # これにより、同じ得点の場合は出席番号が小さい方が優先される
            if score > max_score:
                max_score = score
                ans_id = i + 1
                
    # 結果を出力（合格者がいない場合は初期値の -1 が出力される）
    print(ans_id)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.