Overview

For each observation point, this problem asks us to find the maximum value of “maximum \(-\) minimum” in any contiguous window of length \(K\), and count the number of points where this value is at least the threshold \(T\).

Analysis

For the temperature sequence \(S_{i,1}, S_{i,2}, \ldots, S_{i,M}\) of each observation point, there are \(M-K+1\) contiguous windows of length \(K\) in total.

For example, when \(M=5\) and \(K=3\), the \(3\) windows to consider are:

• \(S_{i,1}, S_{i,2}, S_{i,3}\)
• \(S_{i,2}, S_{i,3}, S_{i,4}\)
• \(S_{i,3}, S_{i,4}, S_{i,5}\)

For each window, we find the maximum and minimum values, and the maximum difference among all windows is the “temperature variation score” for that observation point.

Naive Approach

If we find the maximum and minimum values for each window individually, it takes \(O(K)\) time per window.

Since there are \(O(M)\) windows per observation point, this takes \(O(MK)\) time per point, resulting in \(O(NMK)\) overall.

The constraints state \(N \times M \leq 2 \times 10^6\), but since \(K\) can be up to \(10^5\), this approach will TLE (Time Limit Exceeded).

Key Observation

As we move to the next contiguous window of length \(K\), it only shifts to the right by one element.

That is, when moving to the next window:

• One element is removed from the left end
• One new element is added to the right end

and nothing else changes.

The maximum and minimum values in such a “sliding window” can be efficiently managed using a double-ended queue (deque).

Algorithm

For each observation point, we do the following:

• Prepare dqMax to manage candidates for the maximum value in the window.
• Prepare dqMin to manage candidates for the minimum value in the window.

Managing the Maximum

We maintain elements in dqMax in descending order of their values.

When adding a new value \(x\):

• Any values at the back of the queue that are less than or equal to \(x\) can never be the maximum in any future windows.
• Therefore, we remove them.

As a result, the front of dqMax will always represent the maximum value of the current window.

Managing the Minimum

We maintain elements in dqMin in ascending order of their values.

When adding a new value \(x\):

• Any values at the back of the queue that are greater than or equal to \(x\) can never be the minimum in any future windows.
• Therefore, we remove them.

As a result, the front of dqMin will always represent the minimum value of the current window.

Removing Out-of-Window Elements

If the current index is \(j\), the left boundary of the window of length \(K\) is:

\(left = j - K + 1\)

If the index of the element at the front of the deque is less than \(left\), it means the element has fallen out of the current window, so we remove it from the front.

Checking the Condition

Once \(j \geq K-1\), we have a complete window of length \(K\).

At this point, we calculate:

\(diff = \text{current maximum} - \text{current minimum}\)

If \(diff \geq T\), then this observation point satisfies the condition.

If there is at least one window that satisfies the condition for a given observation point, we increment our answer by \(1\).

Complexity

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

Each element is added to and removed from the deque at most once.

Thus, the time complexity is \(O(M)\) per observation point, and \(O(NM)\) in total.

Moreover, since the number of elements stored in the deque is at most \(K\) (the window size), the space complexity is \(O(K)\).

Implementation Details

• Prepare separate deques for the maximum and minimum values.

• Store both the value and its index in the deque to easily determine if an element has fallen out of the window.

• Since temperatures and differences can be up to \(10^9\) or \(2 \times 10^9\), it is safer to use long long (or appropriate 64-bit integer types).

• If \(T=0\), the difference between the maximum and minimum is always at least \(0\), meaning all observation points satisfy the condition. In this case, you can immediately output \(N\).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    long long T;
    cin >> N >> M >> K >> T;

    if (T == 0) {
        cout << N << '\n';
        return 0;
    }

    int ans = 0;

    for (int i = 0; i < N; i++) {
        deque<pair<int, long long>> dqMax, dqMin;
        bool ok = false;

        for (int j = 0; j < M; j++) {
            long long x;
            cin >> x;

            while (!dqMax.empty() && dqMax.back().second <= x) dqMax.pop_back();
            dqMax.emplace_back(j, x);

            while (!dqMin.empty() && dqMin.back().second >= x) dqMin.pop_back();
            dqMin.emplace_back(j, x);

            int left = j - K + 1;
            while (!dqMax.empty() && dqMax.front().first < left) dqMax.pop_front();
            while (!dqMin.empty() && dqMin.front().first < left) dqMin.pop_front();

            if (j >= K - 1) {
                long long diff = dqMax.front().second - dqMin.front().second;
                if (diff >= T) ok = true;
            }
        }

        if (ok) ans++;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.