Overview

Given test results of students lined up in attendance number order, count the number of contiguous intervals where scores are at least the passing score \(K\).

Analysis

In this problem, we call students whose scores are at least the passing score \(K\) “passers,” and treat consecutive passers as one group. For example, if the scores are \([60, 70, 40, 80, 90]\) and the passing score is \(70\), the indices of passers are \(1, 3, 4\) (0-indexed), but only \([3, 4]\) are consecutive, so the number of groups is 2.

To count the number of contiguous intervals like this, we only need to detect the starting point of each interval. In other words, we can determine that a new group has started at the moment when “the previous student failed and the current student passed.”

A brute-force approach of searching for intervals and counting groups could take \(O(N^2)\) in the worst case, which would not be fast enough for the constraint \(N \leq 2 \times 10^5\). However, by only looking at “the starting point of each interval” as described above, we can find the answer in a single scan.

Algorithm

1. Scan through the student score list \(A\) from the beginning.
2. For each student, determine whether their score \(A_i \geq K\).
3. If “the previous student failed” and “the current student passed,” consider this the start of a new contiguous interval and increment the count.
4. For this check, use a flag in_streak to track “whether we are currently inside a contiguous interval.”
5. Output the final count.

Concrete Example

Input:

5 70
60 80 90 40 70

• Scores: [60, 80, 90, 40, 70]
• Passers: x, o, o, x, o (o means passed)

Contiguous intervals: - [80, 90] → 1 group - [70] → 1 group

A total of 2 award ceremonies are needed.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• By using the flag variable in_streak, we can accurately detect the starting point of each contiguous interval.

• Since we process elements sequentially from the first one, there are no special boundary conditions to worry about.

• Even when there are no passers at all, the count is never incremented, so the answer naturally becomes \(0\).

  Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))

count = 0
in_streak = False

for i in range(N):
    if A[i] >= K:
        if not in_streak:
            count += 1
            in_streak = True
    else:
        in_streak = False

print(count)

---

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