Overview

Given the congestion status of each section of a highway, an emergency report is issued when the length of consecutive congested sections is \(K\) or more. The task is to find the total number of reports.

Analysis

The essence of the problem is to detect consecutive congested sections (consecutive parts where \(S_i = 1\)) and determine whether their length is at least the threshold \(K\). A straightforward approach is sufficient: detect all consecutive congested sections, calculate their lengths, and check whether each is \(K\) or more.

Since the input size can be as large as \(2 \times 10^5\), an efficient algorithm is required. However, since we only need to scan through the consecutive congested sections once, the problem can be processed in linear time.

Algorithm

1. Read \(N\), \(K\), and the list of section states \(S\) from the input
2. Initialize a variable current_length to track the length of the current consecutive congested section, and a variable report_count to track the number of reports
3. Scan each section in order:
   • If it is a congested section (\(S_i = 1\)): increment current_length by 1
   • If it is a normal section (\(S_i = 0\)): if the current consecutive congested section length is \(K\) or more, increment the report count by 1, then reset current_length
4. After the scan is complete, check whether the remaining current_length is \(K\) or more, in case the last section ends with congestion
5. Output the report count

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Report determination is only performed when a consecutive congested section ends (i.e., when \(S_i = 0\) is encountered)

• Since congestion may continue up to the last section, it is necessary to check the remaining length after the loop ends

• Reading the input all at once and storing it as a list allows for efficient processing

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    s_list = list(map(int, data[2:2+n]))
    
    count = 0
    current_length = 0
    report_count = 0
    
    for i in range(n):
        if s_list[i] == 1:
            current_length += 1
        else:
            if current_length >= k:
                report_count += 1
            current_length = 0
    
    if current_length >= k:
        report_count += 1
        
    print(report_count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.