Overview

In an orchard consisting of \(N\) trees, the problem asks to find the length of the longest “contiguous interval” such that the sweetness of every tree in that interval falls within a specified range \([L, R]\).

Analysis

The key insight of this problem is that “the moment a tree that does not satisfy the condition appears, the consecutive streak up to that point is broken.”

For example, consider sweetness values [10, 12, 5, 11, 13] with the criteria being at least 10 and at most 15: 1. 10: Within range (length 1) 2. 12: Within range (length 2) 3. 5: Out of range! (The streak is broken here. Length resets to 0) 4. 11: Within range (length 1) 5. 13: Within range (length 2)

In this way, by checking trees sequentially from one end, “incrementing the count while the condition is satisfied and resetting when it is not,” we can exhaustively examine all candidate intervals without missing any.

Why can’t we use brute force?

If we try to check all intervals \([l, r]\) by brute force, there are approximately \(\frac{N^2}{2}\) combinations of intervals. When \(N = 2 \times 10^5\), the number of computations would be about \(2 \times 10^{10}\), which is far too slow to fit within a typical time limit (around 2 seconds). Therefore, we need an efficient algorithm that produces the answer by scanning the array just once.

Algorithm

We prepare a variable cur_len to hold “the current consecutive length” and a variable max_len to hold “the maximum length so far.”

1. Check the sweetness \(T_i\) of each tree one by one from left to right.
2. If \(L \leq T_i \leq R\):
   • Add \(1\) to the current consecutive length cur_len.
   • Update max_len with max(max_len, cur_len).
3. If it is out of range:
   • Since the streak is broken, reset cur_len to \(0\).
4. After checking all trees, max_len is the answer.

This approach is closely related to what is known as a “scan” or “greedy” method, and it is very efficient.

Complexity

• Time Complexity: \(O(N)\) Since we check each of the \(N\) trees exactly once from start to end, the computation finishes in time proportional to the number of trees.
• Space Complexity: \(O(N)\) Memory is used to store the \(N\) input data values as a list (array).

Implementation Notes

• Fast I/O: When processing input of scale \(N=2 \times 10^5\) in Python, reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), which helps reduce execution time.

• Initial Values: If there is no interval that satisfies the condition, setting the initial value of max_len to 0 ensures that 0 is correctly output.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してトークン化します。
    # 大量の入力を処理する場合、sys.stdin.read().split() は高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目の N (木の本数), L (糖度の下限), R (糖度の上限) を取得します。
    n = int(input_data[0])
    l = int(input_data[1])
    r = int(input_data[2])
    
    # 2行目の各木の糖度 T_i を整数に変換するイテレータを作成します。
    # input_data[3:3+n] により、T_1 から T_N までのトークンをスライスします。
    t_values = map(int, input_data[3:3+n])
    
    max_len = 0
    cur_len = 0
    
    # 各木の糖度を順番にチェックし、条件を満たす連続区間の長さを計算します。
    for val in t_values:
        if l <= val <= r:
            # 糖度が [L, R] の範囲内であれば、現在の連続長をインクリメントします。
            cur_len += 1
            # これまでの最大長を更新します。
            if cur_len > max_len:
                max_len = cur_len
        else:
            # 範囲外の糖度が見つかった場合、現在の連続長をリセットします。
            cur_len = 0
    
    # 条件を満たす連続区間の最大長を出力します。
    print(max_len)

if __name__ == '__main__':
    solve()

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