Overview

This problem asks us to count the number of times Takahashi (student number \(2\)) feels frustrated during the process of distributing stickers in order. Specifically, at the moment Takahashi receives a sticker, we need to determine whether any student has more stickers than him.

Analysis

Key Observation

Takahashi can only feel frustrated at the exact moment a sticker is given to him. At that timing, we need to determine whether “there exists at least one student who has more stickers than Takahashi.”

Problem with the Naive Approach

If we scan all \(N\) students to find the maximum sticker count every time Takahashi receives a sticker, the worst-case time complexity is \(O(N \times M)\). When \(N, M\) can be up to \(3 \times 10^5\), this may result in TLE.

Solution: Efficiently Maintaining the Maximum Value Excluding Takahashi

“Is there a student with more stickers than Takahashi?” can be determined by checking whether the maximum number of stickers held by any student other than Takahashi is greater than Takahashi’s sticker count.

The crucial insight here is that sticker counts can only increase, never decrease. Therefore, “the maximum sticker count among students other than Takahashi (max_count)” is monotonically non-decreasing. By maintaining this with a single variable, we eliminate the need to scan all students each time.

Specifically: - When a sticker is given to a student other than Takahashi → update max_count if that student’s count exceeds it - When a sticker is given to Takahashi → if max_count > takahashi_count, increment frustration count by 1

Algorithm

1. Prepare an array count to track each student’s sticker count, initialized to \(0\).
2. Initialize max_count (the maximum sticker count among students other than Takahashi) to \(0\).
3. Distribute stickers one by one in order:
   • Increment count for student number \(P_i\) by \(1\).
   • If \(P_i \neq 2\): update max_count if count[P_i] is greater than max_count.
   • If \(P_i = 2\): update Takahashi’s count, and if max_count > takahashi_count, increment answer by \(1\).
4. Output the final answer.

Concrete Example

For \(N=3, M=7, P = [1, 1, 2, 1, 2, 2, 1]\):

\(i\)	\(P_i\)	count[1]	count[2]	max_count	Judgment
1	1	1	0	1	-
2	1	2	0	2	-
3	2	2	1	2	\(2 > 1\) → Frustrated!
4	1	3	1	3	-
5	2	3	2	3	\(3 > 2\) → Frustrated!
6	2	3	3	3	\(3 > 3\) is false → No frustration
7	1	4	3	4	-

Answer: 2 times

Complexity

• Time complexity: \(O(M)\) — \(O(1)\) processing per sticker distribution
• Space complexity: \(O(N)\) — array to track each student’s sticker count

Implementation Notes

• Note that max_count tracks “the maximum sticker count among students other than Takahashi.” Even when Takahashi’s own sticker count increases, max_count is not updated.

• Since sticker counts are monotonically non-decreasing, maintaining the maximum is as simple as “update if the current value exceeds the current maximum” (no need to handle decreases).

• By using sys.stdin.buffer.read() to read all input at once, the solution can run efficiently even in Python.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    
    count = [0] * (N + 1)
    takahashi_count = 0
    answer = 0
    max_count = 0
    
    for i in range(M):
        p = int(input_data[2 + i])
        count[p] += 1
        if p != 2:
            if count[p] > max_count:
                max_count = count[p]
        else:
            takahashi_count = count[2]
            if max_count > takahashi_count:
                answer += 1
    
    print(answer)

main()

---

This editorial was generated by claude4.6opus-thinking.