Overview

Given a row of streetlights, we calculate the minimum value (safety level) over consecutive intervals of \(K\) streetlights. A specific streetlight \(T\) is turned off (value \(0\)), and we need to find the maximum safety level among all intervals that include streetlight \(T\).

Analysis

The essence of the problem is: with streetlight \(T\) fixed at \(0\), find the maximum among the minimum values of all contiguous subarrays of length \(K\) that include \(T\). A naive approach would compute the minimum for each interval containing \(T\) (up to \(K\) possible values of \(l\)), taking \(O(K^2)\) time. Since \(K\) can be as large as \(5 \times 10^5\), this won’t fit within the time limit. To solve this efficiently, we use a sliding window minimum technique with a double-ended queue (deque), which computes the result in \(O(N)\) time.

Algorithm

1. Input Processing: Read the number of streetlights \(N\), interval length \(K\), the streetlight to turn off \(T\) (adjusted to \(0\)-indexed), and the brightness array \(S\). Set \(S[T]\) to \(0\).
2. Determining the range of \(l\): Intervals of length \(K\) that include \(T\) have \(l\) ranging from \(\max(0, T - K + 1)\) to \(\min(n - K, T)\).
3. Sliding Window Minimum Computation:
   • Use a deque to maintain indices of elements that could be the minimum within the current window.
   • Scan the array from left to right, and at each step:
     • Remove indices from the front of the deque that have fallen outside the window.
     • If the current element is smaller than the element at the back of the deque, remove the back (once a smaller value arrives, older larger values are no longer needed).
     • Add the current index to the deque.
   • Once the window is fully formed (\(i \geq K-1\)), the front of the deque gives the minimum of the current window.
4. Recording Valid Minimums: Only when the current window includes streetlight \(T\) (\(l \leq T \leq i\)), record the minimum and update the maximum value.
5. Output the Result: Output the obtained maximum safety level.

Complexity

• Time Complexity: \(O(N)\)
  • Each element is added to the deque at most once and removed at most once, so the total time is \(O(N)\).
• Space Complexity: \(O(N)\)
  • Storing array \(S\) takes \(O(N)\), and the deque size is at most \(O(N)\).

Implementation Notes

• By storing indices in the deque and comparing using array values, we can efficiently remove elements outside the window and track the minimum.

• Since we only consider windows that include \(T\), we check whether \(l\) (the starting index of the window) is such that \(T\) falls within the window.

• Although we modify the original array \(S\), it suffices to only set \(S[T]\) to \(0\) as per the problem’s conditions (there is no need to restore it afterward).

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().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に設定
    original_T = S[T]
    S[T] = 0
    
    # 条件を満たすlの範囲を計算
    left_bound = max(0, T - k + 1)
    right_bound = min(n - k, T) + 1
    
    # スライディングウィンドウ最小値（両端キューを使用）
    dq = deque()
    result = -10**18
    
    # 左から右にウィンドウを動かしながら最小値を追跡
    for i in range(n):
        # ウィンドウからはみ出た要素を削除
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # 新しい要素がキュー内の要素より小さい場合、不要な要素を削除
        while dq and S[dq[-1]] >= S[i]:
            dq.pop()
        
        dq.append(i)
        
        # ウィンドウが完全に範囲内にある場合のみ最小値を計算
        if i >= k - 1:
            window_min = S[dq[0]]
            l = i - k + 1
            # 街灯Tを含むウィンドウのみを考慮
            if l <= T <= i:
                if window_min > result:
                    result = window_min
    
    # 元の値を戻す（必要ないが）
    S[T] = original_T
    
    print(result)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.