Overview

This problem asks us to determine whether there exists a position in the sequence \(H_1, H_2, \ldots, H_N\) where the same value appears consecutively \(K\) or more times.
By scanning from left to right and counting how many times the same height appears consecutively, we can determine this efficiently.

Analysis

A flat segment is a contiguous interval of length \(K\) in which all values are equal.

In other words, the condition for an interval to be flat is:

\(H_l = H_{l+1} = \cdots = H_{l+K-1}\)

This is equivalent to checking whether there exists a position where the same value appears \(K\) consecutive times.

Naive Approach

One could consider checking, for each starting point \(l\), whether all values in the interval \([l, l+K-1]\) are equal.

However, this method requires up to \(K\) comparisons to check each interval, and there are up to \(N-K+1\) starting points, so the time complexity is roughly:

\(O(NK)\)

Given the constraint \(N \leq 2 \times 10^5\), \(K\) can also be of the same order, so this method is too slow.

Key Insight

What we need is not to check every interval of exactly length \(K\), but rather to track how many consecutive elements have the same value.

For example, given the sequence:

\([5, 5, 5, 2, 2, 7, 7, 7, 7]\)

The consecutive counts are:

• \(5\) appears \(3\) times consecutively
• \(2\) appears \(2\) times consecutively
• \(7\) appears \(4\) times consecutively

If any of these consecutive counts is \(K\) or more, a flat segment exists.

How to Solve It

It suffices to scan the values from left to right while maintaining:

• The previous value prev
• How many times that value has appeared consecutively cnt

For each newly read value x:

• If x == prev, then cnt += 1
• If x != prev, the consecutive run is broken, so set prev = x, cnt = 1

During this process, if cnt >= K is ever reached, a flat segment of length \(K\) is guaranteed to exist, and we can immediately output Yes.

Algorithm

1. If \(K = 1\), any single element by itself has all heights equal, so a flat segment always exists. Output Yes.
2. Read the first height and store it in prev.
3. Set cnt = 1 to represent the consecutive count of the same height.
4. Read the remaining \(N-1\) heights one by one.
   • Let x be the currently read value.
   • If x == prev, then cnt += 1
     • If cnt >= K, output Yes and terminate.
   • If x != prev, then
     • prev = x
     • cnt = 1
5. If cnt >= K is never reached by the end, output No.

Example

For instance, suppose:

\(N=7, K=3\)
The height sequence is:

\([4, 4, 1, 1, 1, 2, 2]\)

• First \(4\): cnt = 1
• Next \(4\): cnt = 2
• Next \(1\): value changes, so cnt = 1
• Next \(1\): cnt = 2
• Next \(1\): cnt = 3

At this point cnt >= K, so the answer is Yes.

Complexity

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

Implementation Notes

• \(K = 1\) always satisfies the condition, so handling it as a special case at the beginning keeps the code concise.

• There is no need to store the entire array; only the previous value and the consecutive count are needed for the determination.

• When the value changes, don’t forget to reset the consecutive count to \(1\).

• This implementation reads input one element at a time and processes it on the fly, which is also memory-efficient.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())

    if K == 1:
        print("Yes")
        return

    prev = int(input())
    cnt = 1

    for _ in range(N - 1):
        x = int(input())
        if x == prev:
            cnt += 1
            if cnt >= K:
                print("Yes")
                return
        else:
            prev = x
            cnt = 1

    print("No")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.