Overview

This problem involves performing multiple updates on a list of student grades, and then counting how many students have scores below a threshold.

Analysis

Problem Organization

In this problem, we process as follows: 1. Receive the initial scores of \(N\) students 2. Apply \(M\) updates (rewriting a specific student’s score) in order 3. Count the number of students with scores below \(K\) points at the end

Key Observations

• Note that the same student may be updated multiple times
• For example, if student 1’s score is updated twice as “50→70→30”, the final score is 30 points
• In other words, by applying each update in order, the scores are naturally overwritten to the latest values

Why This Problem is Easy

• No complex algorithms are needed; simply simulating (processing as instructed) is sufficient
• Each update only rewrites the corresponding position in the array, so it can be processed in \(O(1)\)

Algorithm

1. Initialization: Store the students’ scores in array Q

2. Update Processing: Process \(M\) updates in order

   • For each update, rewrite student number \(P\)’s score to \(V\)
   • Since student numbers start from 1 (1-indexed), we use P - 1 to convert to the array index (0-indexed)

3. Counting: Traverse the final array Q and count the number of students with scores below \(K\) points

Concrete Example

Input example: \(N=3, M=2, K=50\), initial scores \([40, 60, 30]\) - Update 1: Change student 1’s score to 55 → \([55, 60, 30]\) - Update 2: Change student 3’s score to 70 → \([55, 60, 70]\) - Number of students below 50 points is 0

Complexity

• Time Complexity: \(O(N + M)\)

  • Reading initial scores: \(O(N)\)
  • \(M\) update operations: Each is \(O(1)\), so total is \(O(M)\)
  • Final counting: \(O(N)\)

• Space Complexity: \(O(N)\)

  • Only the array storing students’ scores

Implementation Notes

1. Index Conversion: In the problem statement, student numbers start from 1 (1-indexed), while Python arrays start from 0 (0-indexed), so adjustment like Q[P - 1] is necessary

2. When Number of Updates is 0: The case \(M = 0\) is possible, but since the for loop simply executes 0 times, no special handling is needed

3. Ways to Write the Count: In Python, using a generator expression like sum(1 for score in Q if score < K) is concise. len([score for score in Q if score < K]) gives the same result

Source Code

# Receive input
N, M, K = map(int, input().split())
Q = list(map(int, input().split()))

# Process M updates
for _ in range(M):
    P, V = map(int, input().split())
    Q[P - 1] = V  # Adjust since student numbers are 1-indexed

# Count the number of students with scores below K
count = sum(1 for score in Q if score < K)

# Output the result
print(count)

---

This editorial was generated by claude4.5opus.