Overview

This is a problem where you update students’ scores and ultimately determine the number of students who need supplementary lessons.

Analysis

In this problem, the initial scores of each student are given first, followed by several update operations that change specific students’ scores. After all updates are completed, we need to count the number of students whose scores are less than \(K\) points.

A naive approach might involve counting the students needing supplementary lessons after every update, but this includes many unnecessary computations and is not efficient. Additionally, since the maximum score is \(100\) points, we can notice that the range of scores is limited, but this property does not directly lead to speedup for this problem.

The simplest and most efficient approach is to process all updates directly on the array, and then scan all students’ scores just once at the end to count those needing supplementary lessons. This avoids unnecessary computations and runs sufficiently fast.

Algorithm

1. First, store the initial scores of \(N\) students in a list scores.
2. Next, for each of the \(M\) updates, overwrite the specified student’s score with the new value. Since the student numbers given in the input are 1-indexed, subtract 1 to match the list index (0-indexed).
3. After all updates are completed, check each score in the list to determine whether it is less than \(K\), and count the number of qualifying students.
4. Output the count result.

For example, given the following input:

3 2 60
50 70 80
1 65
3 40

• Initial state: [50, 70, 80]
• 1st update (change student 1’s score to 65) → [65, 70, 80]
• 2nd update (change student 3’s score to 40) → [65, 70, 40]
• In the end, there is 1 person with a score less than 60 (student 3).

Complexity

• Time complexity: \(O(N + M)\)
  • Reading the initial scores takes \(O(N)\), processing updates takes \(O(M)\), and the final count takes \(O(N)\).
• Space complexity: \(O(N)\)
  • The list scores that holds the students’ scores uses \(O(N)\) memory.

Implementation Notes

• Since student numbers are given as 1-indexed, you must always subtract 1 when accessing list indices.

• It is important that the final counting process is performed only after all update operations are completed.

  Source Code

# 入力を受け取る
N, M, K = map(int, input().split())
scores = list(map(int, input().split()))

# 更新処理
for _ in range(M):
    p, v = map(int, input().split())
    scores[p - 1] = v

# 補習対象の人数をカウント
count = 0
for score in scores:
    if score < K:
        count += 1

# 結果を出力
print(count)

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