Overview

Given a road consisting of \(N\) sections, the problem asks us to identify “clusters” of consecutive congested sections (sections with value \(1\)) and count how many of these clusters have a length of \(K\) or more.

Analysis

The key to solving this problem is to accurately determine “where congestion starts and where it ends.”

For example, consider the case where \(K=3\) and the state is 1 1 1 0 1 1 1 1 0 1. 1. First, there are \(3\) consecutive 1s. The length is \(3\), which is \(K\) or more, so this qualifies for an emergency report. 2. Next, a 0 appears, so we reset the count. 3. After that, there are \(4\) consecutive 1s. The length is \(4\), which is also \(K\) or more, so this qualifies for an emergency report. 4. Finally, there is a single 1, but its length of \(1\) is less than \(K\), so it is not reported.

In this way, we can see that we should scan the list from the beginning, “incrementing the count while 1s continue, and when a 0 appears, checking the count and resetting it.”

An important note: we must not forget to handle “the case where the last section is 1.” Immediately after the loop ends, we must check whether the remaining count is \(K\) or more.

Algorithm

We perform the simulation with the following steps:

1. Initialize the number of emergency reports (emergency_reports) and the current consecutive congestion count (current_consecutive_count) to \(0\).
2. Check the state \(S_i\) of each section sequentially from \(i=1\) to \(N\).
   • If \(S_i = 1\): increment current_consecutive_count by \(1\).
   • If \(S_i = 0\):
     • If current_consecutive_count is \(K\) or more, increment emergency_reports by \(1\).
     • Reset current_consecutive_count to \(0\).
3. After all checks are complete, if current_consecutive_count is \(K\) or more, increment emergency_reports by \(1\).
4. Output emergency_reports.

Complexity

• Time complexity: \(O(N)\)
  • Since we only scan the list once from end to end, the processing completes in linear time with respect to the number of sections \(N\). This is sufficiently fast even under the constraint \(N \le 2 \times 10^5\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the \(N\) input elements as a list.

Implementation Notes

• Reading input: Since \(N\) can be large, we use sys.stdin.read().split() to read input efficiently.

• Post-loop processing: If the end of the road (section \(N\)) is congested (\(1\)), no 0 is encountered within the loop, so the report check is never triggered. Therefore, the final check must be performed outside the loop.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してトークンのリストを作成します。
    # これにより、改行やスペースに関わらずデータを取得できます。
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 区間の数 N と、緊急報告の閾値 K を取得します。
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各区間の状態 S_1, ..., S_N を取得します。
    # 文字列として比較するため、intへの変換は行わずそのまま扱います。
    s_list = input_data[2:2+n]
    
    emergency_reports = 0
    current_consecutive_count = 0
    
    # 各区間の状態を順番に確認します。
    for s in s_list:
        if s == '1':
            # 渋滞中の場合、現在の連続カウントを増やします。
            current_consecutive_count += 1
        else:
            # 通常の状態に戻った場合、それまでの連続渋滞区間（かたまり）を処理します。
            if current_consecutive_count >= k:
                # かたまりの長さが K 以上であれば、緊急報告を 1 回行います。
                emergency_reports += 1
            # カウントをリセットします。
            current_consecutive_count = 0
    
    # 全区間の確認が終わった後、最後の区間まで渋滞が続いていた場合の処理を行います。
    if current_consecutive_count >= k:
        emergency_reports += 1
        
    # 結果を出力します。
    print(emergency_reports)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.