Overview

For each observation site, we examine the “maximum value \(-\) minimum value” for each contiguous interval of length \(K\), and find the number of sites where the maximum of these differences is at least \(T\).

Analysis

Let the temperature data at a certain observation site be \(S_1, S_2, \ldots, S_M\).

What we want to determine is whether there is any interval of length \(K\) for which the calculated value of

\[ \max(S_l, \ldots, S_{l+K-1}) - \min(S_l, \ldots, S_{l+K-1}) \]

is at least \(T\).

In other words, for each observation site, we only need to determine:

Whether there exists an interval of length \(K\) in which the difference between the maximum and minimum values is at least \(T\).

If we naively compute the maximum and minimum values for each interval, it takes

\[ O((M-K+1)K) \]

per observation site.

Under the constraints, \(N \times M \leq 2 \times 10^6\), but since \(K\) can be up to \(10^5\), this approach will not run in time.

Therefore, we need to efficiently manage the maximum and minimum values for a sliding window of length \(K\).

In this problem, by using a monotonic queue, we can process each observation site in \(O(M)\).

Algorithm

For each observation site, we iterate through the temperature data from left to right.

Let \(i\) be the current position we are looking at. The current interval of length \(K\) is

\[ [i-K+1, i] \]

To find the maximum and minimum values of this interval quickly, we prepare the following two queues:

• Queue for maximums qmax
  • Maintained in descending order of values.
  • The front of the queue represents the maximum value in the current interval.
• Queue for minimums qmin
  • Maintained in ascending order of values.
  • The front of the queue represents the minimum value in the current interval.

We store the array indices in the queues instead of the values themselves.

This is to determine whether elements have fallen out of the current interval.

Updating the Queue for Maximums

When adding a new value \(x = S_i\), if the value at the back of the queue is less than or equal to \(x\), those elements have no chance of becoming the maximum in the future.

Therefore, we remove them from the back.

After that, we append the index \(i\).

This ensures that the values in the queue are always in descending order.

Updating the Queue for Minimums

Similarly, when adding a new value \(x = S_i\), if the value at the back of the queue is greater than or equal to \(x\), we remove it.

After that, we append the index \(i\).

This ensures that the values in the queue are always in ascending order.

Removing Out-of-Interval Elements

Since the current interval is \([i-K+1, i]\), any index less than or equal to

\[ i-K \]

is outside the interval.

If such an index is at the front of the queue, we pop it from the front.

Checking the Condition

Once \(i \geq K-1\), an interval of length \(K\) is fully formed.

At this point,

• The maximum value is a[qmax[hmax]]
• The minimum value is a[qmin[hmin]]

Thus, if

\[ a[qmax[hmax]] - a[qmin[hmin]] \geq T \]

holds, then this observation site satisfies the condition.

If we find even one interval that satisfies the condition, the observation site is counted towards the answer, so we do not need to check the rest of that row.

Complexity

• Time Complexity: \(O(NM)\)
• Space Complexity: \(O(M)\)

Each element is added to and removed from the maximum and minimum queues at most once.

Therefore, we can process each observation site in \(O(M)\).

Implementation Details

In this code, we handle several edge cases beforehand.

Case \(T = 0\)

The difference between the maximum and minimum values is always at least \(0\).

Therefore, all observation sites satisfy the condition, so the answer is \(N\).

Case \(K = 1\)

In an interval of length \(1\), the maximum and minimum values are the same, so the difference is always \(0\).

However, since the case \(T = 0\) is already handled, we have \(T > 0\) here.

Thus, no observation site satisfies the condition, so the answer is \(0\).

Case \(K = M\)

There is only one interval, which spans the entire array.

Therefore, for each observation site, it is sufficient to simply calculate:

\[ \max(a) - \min(a) \]

Queue Implementation

While you can use Python’s collections.deque, in this code, we implement the queue using arrays with head and tail pointers for optimization.

• hmax, tmax: The head and tail of the queue for maximums
• hmin, tmin: The head and tail of the queue for minimums

The arrays qmax and qmin store the indices, and the actual values are accessed via a[index].

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M, K, T = map(int, input().split())

    if T == 0:
        print(N)
        return

    if K == 1:
        print(0)
        return

    ans = 0

    if K == M:
        for _ in range(N):
            a = list(map(int, input().split()))
            if max(a) - min(a) >= T:
                ans += 1
        print(ans)
        return

    qmax = [0] * M
    qmin = [0] * M
    k1 = K - 1

    for _ in range(N):
        a = list(map(int, input().split()))

        hmax = tmax = 0
        hmin = tmin = 0

        for i, x in enumerate(a):
            while tmax > hmax and a[qmax[tmax - 1]] <= x:
                tmax -= 1
            qmax[tmax] = i
            tmax += 1

            while tmin > hmin and a[qmin[tmin - 1]] >= x:
                tmin -= 1
            qmin[tmin] = i
            tmin += 1

            limit = i - K
            if qmax[hmax] <= limit:
                hmax += 1
            if qmin[hmin] <= limit:
                hmin += 1

            if i >= k1 and a[qmax[hmax]] - a[qmin[hmin]] >= T:
                ans += 1
                break

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.