Overview

This problem asks us to determine, for each observation site based on the temperature data of the past \(M\) days, “whether there exists at least one contiguous interval of length \(K\) where the (maximum value - minimum value) is at least \(T\).”

We perform this check for all observation sites and find the total number of sites that satisfy the condition.

Analysis

Naive Approach and Its Limitations

The simplest method is to naively check all intervals of length \(K\) for each observation site. There are \(M - K + 1\) possible starting positions for the interval, and finding the maximum and minimum values within each interval takes \(O(K)\) time. In this case, the time complexity per observation site would be \(O((M - K) \times K)\).

In the worst-case scenario (e.g., \(M = 10^5, K = 5 \times 10^4\)), this would require approximately \(2.5 \times 10^9\) operations per observation site. Since we have \(N\) sites, this will easily exceed the time limit (typically 2 seconds), resulting in a TLE (Time Limit Exceeded).

Efficient Approach

When sliding the interval to the right by one step, only one element enters the interval and only one element leaves it. Utilizing this property, we need to efficiently update the maximum and minimum values within the interval.

This is a famous problem known as the “sliding window minimum (maximum)” problem. By using a double-ended queue (deque), we can solve it in \(O(M)\) time per observation site by scanning the data from left to right exactly once.

Algorithm

Sliding Window Maximum and Minimum Algorithm

Using a double-ended queue (deque), we maintain a list of indices that are “currently inside the interval (of length \(K\))” and “whose corresponding values are strictly decreasing (or increasing).”

Here, we describe the operation of max_dq for finding the maximum value (the minimum value is analogous, with the inequality signs reversed).

1. Adding a new element \(S[j]\): We inspect the elements at the back of the queue one by one, and as long as their values are less than or equal to \(S[j]\), we remove them (pop). This is because the newly added \(S[j]\) is larger and will remain in the window longer, meaning the elements before it that are less than or equal to \(S[j]\) can never become the maximum in any future window. After that, we append the new index \(j\) to the back.
2. Removing old elements: If the index at the front of the queue is out of the current window’s range (i.e., less than or equal to \(j - K\)), we remove it from the front (popleft).
3. Retrieving the maximum value: By performing the above operations, the index of the maximum value within the current window is always stored at the front of the queue (max_dq[0]).

Concrete Example (for \(K=3\), Array \(S = [2, 5, 3, 1]\))

• \(j=0\) (value: \(2\)): max_dq becomes [0].
• \(j=1\) (value: \(5\)): Since the element \(2\) (index \(0\)) at the back is less than or equal to \(5\), it is removed, and max_dq becomes [1].
• \(j=2\) (value: \(3\)): Since \(3\) is smaller than the \(5\) at the back, it is simply appended, and max_dq becomes [1, 2].
  • At this point, the window length reaches \(K=3\). The maximum value of the current window [2, 5, 3] is S[max_dq[0]] = S[1] = \(5\).
• \(j=3\) (value: \(1\)): \(1\) is appended, making max_dq [1, 2, 3]. However, the front index \(1\) becomes out of the window (though it is not less than or equal to \(3 - 3 = 0\), it will be removed in the next step).

By performing these operations simultaneously with two deques—one for the maximum and one for the minimum—we can check at each step whether (maximum) - (minimum) >= T holds.

Complexity

• Time Complexity: \(O(N \times M)\) For each observation site, each element of the array of length \(M\) is added to and removed from the deque at most once. Thus, the processing time per observation site is \(O(M)\). Repeating this \(N\) times yields an overall time complexity of \(O(N \times M)\), which is sufficiently fast for the constraint \(N \times M \le 2 \times 10^6\).

• Space Complexity: \(O(N \times M)\) We use \(O(N \times M)\) memory to store all the input temperature data. Since the size of the deque is at most \(K\), the additional memory overhead is extremely small.

Implementation Details

1. Fast I/O: In Python, since the number of input lines can be very large, we can significantly reduce the I/O time by reading all inputs at once using sys.stdin.read().split() and converting them into a list of numbers.

2. Early Termination (Pruning): For any observation site, as soon as we find at least one interval that satisfies the condition (i.e., ok = True), we can break out of the search for that site and proceed to the next one. This further reduces the execution time in non-worst-case scenarios.

   Source Code

import sys
from collections import deque


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    all_ints = list(map(int, input_data))
    N, M, K, T = all_ints[:4]

    ans = 0
    start_idx = 4

    for i in range(N):
        S = all_ints[start_idx : start_idx + M]
        start_idx += M

        max_dq = deque()
        min_dq = deque()
        ok = False

        for j in range(M):
            val = S[j]

            # max_dq の更新
            while max_dq and S[max_dq[-1]] <= val:
                max_dq.pop()
            max_dq.append(j)
            if max_dq[0] <= j - K:
                max_dq.popleft()

            # min_dq の更新
            while min_dq and S[min_dq[-1]] >= val:
                min_dq.pop()
            min_dq.append(j)
            if min_dq[0] <= j - K:
                min_dq.popleft()

            if j >= K - 1:
                if S[max_dq[0]] - S[min_dq[0]] >= T:
                    ok = True
                    break

        if ok:
            ans += 1

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.