Overview

In this problem, we are given temperature data of \(M\) days for each of the \(N\) observation sites. For each site, we need to find the “difference between the maximum and minimum values” in any contiguous interval of length \(K\) (sliding window). We then need to count the number of observation sites where the maximum of these differences (the temperature fluctuation score) is at least a threshold \(T\).

Analysis

Naive Approach and Its Limitations

For each observation site, there are \(M - K + 1\) intervals of length \(K\). If we naively find the maximum and minimum values for each interval, it takes \(O(K)\) time per interval. In this case, the time complexity per observation site would be \(O(M \times K)\), leading to an overall time complexity of \(O(N \times M \times K)\).

Looking at the constraints, \(N \times M \leq 2 \times 10^6\) and \(K \leq 10^5\). In the worst-case scenario (e.g., \(N = 20, M = 10^5, K = 5 \times 10^4\)), the overall number of operations would exceed \(10^{11}\), which will result in a Time Limit Exceeded (TLE) error.

Therefore, we need an efficient way to find the maximum and minimum values within a sliding window.

Efficient Solution: Sliding Window Maximum and Minimum

When shifting the interval to the right one element at a time, we can efficiently update and query the maximum and minimum values within the interval in \(O(1)\) time per step (and \(O(M)\) in total) using a double-ended queue (deque). By using this algorithm, we can reduce the processing time per observation site to \(O(M)\), allowing us to solve the entire problem in \(O(N \times M)\) time complexity.

---

Algorithm

Managing the Sliding Window Using Deques

We maintain two deques: dq_max to find the maximum values, and dq_min to find the minimum values. These deques will store the “indices” of the temperature data.

1. Managing the Maximum Values (dq_max)

We maintain dq_max such that the values corresponding to the indices are always in descending order (largest at the front, smallest at the back).

When adding a new element \(S[j]\), we perform the following operations: - While the value corresponding to the index at the back of dq_max is less than or equal to \(S[j]\), remove those elements from the back (since past elements smaller than \(S[j]\) can never be the maximum in any future window). - Append \(j\) to the back of dq_max. - If the index at the front of dq_max falls out of the current window range (i.e., is less than or equal to \(j - K\)), remove it from the front.

Through these operations, the index at the front (head) of dq_max will always represent the index of the maximum value in the current interval \([j - K + 1, j]\).

2. Managing the Minimum Values (dq_min)

Similarly, we maintain dq_min such that the values corresponding to the indices are always in ascending order (smallest at the front, largest at the back).

When adding a new element \(S[j]\): - While the value corresponding to the index at the back of dq_min is greater than or equal to \(S[j]\), remove those elements from the back. - Append \(j\) to the back of dq_min. - If the index at the front of dq_min falls out of the current window range (i.e., is less than or equal to \(j - K\)), remove it from the front.

This ensures that the index at the front of dq_min always represents the index of the minimum value in the current interval.

3. Checking the Condition

At each step \(j \geq K - 1\) (once the first full window is formed), we calculate the difference between the maximum and minimum values of the current interval: mx - mn. If this difference is at least \(T\), we can determine that the temperature fluctuation score for this observation site is at least \(T\).

---

Complexity

• Time Complexity: \(O(N \times M)\)
  • At each observation site, each element is added to and removed from the deque at most once, so the processing time per site is \(O(M)\).
  • Since we do this for \(N\) sites, the overall time complexity is \(O(N \times M)\). This is fast enough to pass within the time limit for the constraint \(N \times M \leq 2 \times 10^6\).
• Space Complexity: \(O(M)\)
  • The memory required to store the temperature data and the deques for a single observation site is \(O(M)\). Since we can reuse this memory when processing the next site, the overall space complexity is kept at \(O(M)\).

---

Implementation Details

1. Custom Deque using Arrays Although std::deque in the C++ standard library is convenient, it can be somewhat slow due to memory allocation overhead. In this implementation, we use a std::vector of size \(M\) and implement a custom deque using head and tail index variables (either as a simple ring buffer or a one-directional array). This significantly speeds up execution by reducing the constant-factor overhead.

2. Early Exit / Early Skip When the Condition is Met During the processing of a single observation site, if the condition “the difference between the maximum and minimum values is at least \(T\)” is met even once, we can immediately confirm that the score for this site is at least \(T\). Thus, we set a flag ok to true and skip subsequent deque updates (if (ok) continue;). Note: To ensure the data for the next observation site is read correctly, we must not skip reading the input (cin >> S[j]) and must read it to the end.

3. Fast I/O Since the number of input elements can be up to \(2 \times 10^6\), which is quite large, we use ios_base::sync_with_stdio(false); cin.tie(NULL); to speed up C++ standard input/output operations.

   Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    long long T;
    if (!(cin >> N >> M >> K >> T)) return 0;

    vector<long long> S(M);
    vector<int> dq_max(M);
    vector<int> dq_min(M);

    int ans = 0;

    for (int i = 0; i < N; ++i) {
        int head_max = 0, tail_max = 0;
        int head_min = 0, tail_min = 0;
        bool ok = false;

        for (int j = 0; j < M; ++j) {
            cin >> S[j];
            if (ok) continue;

            // max deque
            while (tail_max > head_max && S[dq_max[tail_max - 1]] <= S[j]) {
                tail_max--;
            }
            dq_max[tail_max++] = j;
            if (dq_max[head_max] <= j - K) {
                head_max++;
            }

            // min deque
            while (tail_min > head_min && S[dq_min[tail_min - 1]] >= S[j]) {
                tail_min--;
            }
            dq_min[tail_min++] = j;
            if (dq_min[head_min] <= j - K) {
                head_min++;
            }

            if (j >= K - 1) {
                long long mx = S[dq_max[head_max]];
                long long mn = S[dq_min[head_min]];
                if (mx - mn >= T) {
                    ok = true;
                }
            }
        }
        if (ok) {
            ans++;
        }
    }

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

---

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