Overview

After temporarily setting streetlight \(T\) to \(0\), we need to find the minimum value (safety level) of each window of length \(K\) that contains \(T\), and then output the maximum among those minimum values.

Reasoning

First, since streetlight \(T\) is turned off, its value is always \(0\), so we can simply replace the array with \(S_T \leftarrow 0\). Then the safety level of each window is simply “the minimum value of that window.”

Next, “windows of length \(K\) that contain \(T\)” can be expressed in terms of the left endpoint \(l\). Since a window is \([l, l+K-1]\): - Condition for being a valid window of length \(K\): \(0 \le l \le N-K\) - Condition for containing \(T\) (0-indexed as \(t\)): \(l \le t \le l+K-1\)

Therefore, the allowable range for the left endpoint \(l\) is: $\( \max(0, t-K+1) \le l \le \min(t, N-K) \)$ (In the code, we use 0-indexing.)

A naive approach would compute the minimum of \(K\) elements for each \(l\) in \(O(K)\), repeating this for up to \(O(N)\) windows, resulting in worst-case \(O(NK)\), which is far too slow for \(N \le 5\times 10^5\).

Instead, we use a “sliding window minimum” to enumerate the minimum of all windows of length \(K\) in \(O(N)\), then pick only those windows that contain \(T\) and take the maximum.

Algorithm

1. Read input and replace \(S[t]=0\) where \(t=T-1\) (converted to 0-index).
2. Compute the range of left endpoints for windows containing \(T\):
   • \(l_{\min}=\max(0, t-K+1)\)
   • \(l_{\max}=\min(t, N-K)\)
3. Use a deque (double-ended queue) to compute the sliding window minimum for windows of length \(K\).
   • The deque maintains indices such that their corresponding values are monotonically increasing.
   • When inserting a new element \(S[i]\), remove from the back all indices whose values satisfy \(S[\text{back}] \ge S[i]\), then append \(i\).
   • Remove from the front any index that has fallen outside the window (i.e., \(\le i-K\)).
   • This way, the front of the deque always holds the position of the minimum value in the current window.
4. Each time a window is complete (\(i \ge K-1\)), compute the window’s left endpoint \(l=i-K+1\). Only when \(l_{\min} \le l \le l_{\max}\), update the answer (maximum) with \(S[\text{deque front}]\).
5. Output the final maximum value.

As a concrete illustration, imagine listing the minimum values of all windows of length \(K\) from left to right. Among these, only those whose left endpoint ranges from \(l_{\min}\) to \(l_{\max}\) correspond to windows containing \(T\), so we are taking the maximum of that subset.

Complexity

• Time complexity: \(O(N)\) (each element enters and leaves the deque at most once)
• Space complexity: \(O(K)\) (the deque holds at most the window width number of elements)

Implementation Notes

• Working in 0-index makes it easier to write the formulas for the left endpoint range and the deque’s out-of-range checks.

• For the deque’s monotonicity, using “remove from the back if the back value is greater than or equal to the new value (\(\ge\))” keeps the newer element when values are equal, which works well with the out-of-range removal.

• To check “only windows containing \(T\),” we compute all window minimums on the fly and update the answer only when the left endpoint \(l\) falls within the valid range. This eliminates the need for any extra preprocessing.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K, T = map(int, input().split())
    S = list(map(int, input().split()))
    t0 = T - 1
    S[t0] = 0

    l_low = max(0, t0 - K + 1)
    l_high = min(t0, N - K)

    dq = deque()
    ans = -10**30

    for i, x in enumerate(S):
        while dq and S[dq[-1]] >= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - K:
            dq.popleft()

        if i >= K - 1:
            l = i - K + 1
            if l_low <= l <= l_high:
                ans = max(ans, S[dq[0]])

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.