Overview

When one streetlight is turned off, we need to find the maximum of the minimum values (safety levels) across all contiguous intervals of length \(K\) that include that streetlight.

Analysis

In this problem, we temporarily set the brightness of the streetlight at position \(T\) to \(0\), then for all intervals of length \(K\) that include that streetlight, we compute the minimum value (safety level) within each interval, and output the maximum among those minimum values.

A naive approach would enumerate all valid intervals and compute the minimum for each one directly, but this results in at most \(O(NK)\) time complexity, which would cause TLE (Time Limit Exceeded) under the constraint \(N \leq 5 \times 10^5\).

Therefore, we need an algorithm that can efficiently compute interval minimums. In particular, noticing that the interval slides, we can see this is a classic sliding window minimum problem. This can be efficiently computed using a deque (double-ended queue).

Additionally, since we don’t need to consider intervals that don’t include streetlight \(T\), the starting position \(l\) of the interval is restricted as follows: - \(l \leq T\) - \(l + K - 1 \geq T\)

Simplifying this, the range of \(l\) is: $\( \max(0, T - K + 1) \leq l \leq \min(N - K, T) \)$

Algorithm

1. Read the input and change the brightness of streetlight \(T\) to \(0\) (converting to 0-indexed).
2. Based on the conditions above, determine the range \([l_{\min}, l_{\max}]\) of starting positions for the intervals to consider.
3. Use the sliding window minimum technique with a deque to efficiently compute the minimum of each interval.
   • The deque stores indices of elements within the current interval, maintaining their corresponding values in monotonically increasing order.
   • When adding a new element, remove unnecessary elements from the back before inserting.
   • If an element falls outside the interval, remove it from the front.
4. While recording the minimum of each interval, keep updating the maximum value.
5. Output the final maximum value.

Complexity

• Time complexity: \(O(N)\)
  • Each element is added to the deque at most once and removed at most once, so the entire process runs in linear time.
• Space complexity: \(O(K)\)
  • Because the deque stores at most \(K\) elements.

Implementation Notes

• Streetlight numbers are given in 1-indexed form, but converting to 0-indexed for internal processing makes things easier to handle.

• Store indices in the deque and perform comparisons based on their corresponding values.

• It is important to accurately compute the range of starting positions for the intervals.

• At each slide of the interval, check whether the front element of the deque is still within the interval, and remove it if necessary.

  Source Code

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    T = int(data[2]) - 1  # 0-indexed
    S = list(map(int, data[3:3+N]))
    
    # 街灯Tを0にする
    S[T] = 0
    
    # 対象となる区間[l, l+K-1]でTを含むようなlの範囲を求める
    # l <= T かつ l + K - 1 >= T
    # よって max(0, T - K + 1) <= l <= min(N - K, T)
    l_min = max(0, T - K + 1)
    l_max = min(N - K, T)
    
    # 各区間[l, l+K-1]について最小値を求め、その最大値を求める
    # 区間の最小値を効率的に求めるためにdequeを使ったスライディングウィンドウを使う
    
    # 各区間について最小値を求める
    max_safe = float('-inf')
    
    # dequeを初期化して最初の区間[l_min, l_min+K-1]の最小値を求める
    dq = deque()
    # 最初の区間を処理
    for i in range(l_min, l_min + K):
        while dq and S[dq[-1]] >= S[i]:
            dq.pop()
        dq.append(i)
    
    # 最初の区間の最小値をチェック
    current_min = S[dq[0]]
    if current_min > max_safe:
        max_safe = current_min
    
    # スライドしていく
    for l in range(l_min + 1, l_max + 1):
        # 新しく追加される要素のインデックス
        right = l + K - 1
        
        # 古い要素の削除（範囲外になったら）
        if dq and dq[0] < l:
            dq.popleft()
        
        # 新しい要素の追加
        while dq and S[dq[-1]] >= S[right]:
            dq.pop()
        dq.append(right)
        
        # 現在の最小値を取得
        current_min = S[dq[0]]
        if current_min > max_safe:
            max_safe = current_min
            
    print(max_safe)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.