Overview

Among the clusters of consecutive congested sections, count the number of clusters whose length is at least \(K\).

Analysis

In this problem, we need to find each “interval of consecutive \(1\)s” (i.e., congested sections) one by one, and determine whether its length is at least \(K\).

A naive approach would be to count consecutive \(1\)s starting from each index every time, but in the worst case this would examine the same interval multiple times, resulting in a time complexity of \(O(N^2)\). Since \(N\) can be up to \(2 \times 10^5\), this would result in TLE (Time Limit Exceeded).

Instead, we consider a method that scans each “cluster of consecutive \(1\)s” only once. Specifically, when we encounter the start of \(S_i = 1\), we check how far the consecutive \(1\)s extend from that point and calculate the length. This way, we only need to scan the entire array at most once, allowing efficient processing.

For example, given the following input:

N = 10, K = 3
S = [0, 1, 1, 1, 0, 1, 1, 0, 1, 1]

The clusters of consecutive \(1\)s are the following 3: - Sections 2–4: length 3 → emergency report - Sections 6–7: length 2 → normal response - Sections 9–10: length 2 → normal response

Therefore, an emergency report occurs only once.

In this way, by handling consecutive intervals as groups, we eliminate redundant work.

Algorithm

In the code, a while loop is used to scan the array S from the beginning.

1. If the current position i is 1 (congested), mark it as the start of a consecutive segment.
2. From there, use another while loop to advance i as long as S[i] == 1 continues.
3. Finally, compute the length length = i - start from the starting index start to the ending index.
4. If this length is at least \(K\), increment the emergency report count.
5. If S[i] == 0, simply move to the next position.

In this way, we examine all consecutive congested intervals exactly once and perform the necessary checks.

Complexity

• Time complexity: \(O(N)\)
  Since each element is processed at most once, the solution runs in linear time.
• Space complexity: \(O(1)\) (excluding input)
  No additional arrays are used; only a constant number of variables are needed.

Implementation Notes

• Carefully manage the progression of the index (note that i is advanced inside the inner loop)
• Use the start variable to record the beginning of a consecutive interval and correctly compute the length
• In the else clause, when S[i] == 0, simply doing i += 1 is sufficient

## Source Code

```python
N, K = map(int, input().split())
S = list(map(int, input().split()))

count = 0
i = 0
while i < N:
    if S[i] == 1:
        start = i
        while i < N and S[i] == 1:
            i += 1
        length = i - start
        if length >= K:
            count += 1
    else:
        i += 1

print(count)

---

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