Overview

This is a problem where you look at a sequence of intervals represented by \(0/1\) from left to right, and count how many contiguous blocks of \(1\)s (consecutive intervals) have length \(K\) or more.

Analysis

The key observation is that “an emergency report occurs at most once per maximal consecutive block of \(1\)s (a maximal contiguous run of \(1\)s).”
In other words, rather than counting each interval individually, it suffices to know only the length of each contiguous block of \(1\)s.

For example, with \(K=3\): - \(S = [1,1,1,1]\) has one block of length \(4\), so there is \(1\) report - \(S = [1,1,0,1,1,1,0]\) has blocks of length \(2\) and \(3\), so there is \(1\) report

A naive approach like “extending to the right from each position to check the length” could end up examining the same intervals multiple times in the worst case, resulting in \(O(N^2)\) time, which is too slow for \(N \le 2\times 10^5\).
Instead, by scanning from left to right once while keeping track of “how many consecutive \(1\)s we’ve seen so far,” we can process everything without redundancy.

Algorithm

Scan from left to right, maintaining the current run length run of consecutive \(1\)s.

1. Initialize ans = 0, run = 0
2. For each \(S_i\):
   • If \(S_i = 1\), then run += 1
   • If \(S_i = 0\), the previous block of \(1\)s has ended, so:
     • If run >= K, then ans += 1
     • Reset run = 0
3. After the scan, check once more whether run >= K and add to ans if so, to handle the case where the sequence ends with \(1\)
4. Output ans

With this method, each maximal consecutive block of \(1\)s is evaluated exactly once.

Complexity

• Time complexity: \(O(N)\) (only a single scan)
• Space complexity: \(O(1)\) (only a constant number of variables such as ans and run)

Implementation Notes

• It is convenient to perform the block evaluation “at the moment a \(0\) is encountered.”

• If the array ends with \(1\), the last block would remain unprocessed, so don’t forget to add one more check after the loop.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    S = data[2:]

    ans = 0
    run = 0
    for x in S:
        if x == 1:
            run += 1
        else:
            if run >= K:
                ans += 1
            run = 0
    if run >= K:
        ans += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.