Overview

This problem asks us to find, for each of the \(N\) observation sites, the maximum value of the “difference between the maximum and minimum values” within any contiguous \(K\)-day interval over the past \(M\) days, and then count the number of observation sites where this maximum difference is at least the threshold \(T\).

Analysis

• Naive Approach and its Challenges: First, a naive approach would be to find the maximum and minimum values from scratch for every interval of length \(K\). However, finding the maximum and minimum of a single interval takes \(O(K)\) time. Since we need to check \(M-K+1\) intervals for each observation site, this would take \(O(M \times K)\) time per site. Since \(N \times M\) can be up to \(2 \times 10^6\) and \(K\) can be around \(10^5\), the overall time complexity would be \(O(N \times M \times K)\), which results in TLE (Time Limit Exceeded).
• Solution: We focus on the operation of “sliding a contiguous interval to the right”. When moving to the next interval to the right, only one element at the left end is removed, and one element at the right end is added. By using a double-ended queue (deque), a data structure that can efficiently update this interval, we can find the maximum and minimum values of each interval in \(O(1)\) time. This allows us to perform the calculation in \(O(M)\) time per observation site.

Algorithm

We use the “Sliding Window Maximum/Minimum” technique. - We add elements of the array one by one from left to right. - Prepare two queues: a queue for finding the maximum value and a queue for finding the minimum value. - Update rule for the maximum queue: When adding a new element, any elements already in the queue that are less than or equal to the new element can never become the “maximum value” in the future, so we remove them from the queue (checking from the back). This keeps the elements in the queue in “descending order” (from largest to smallest). - Update rule for the minimum queue: Similarly, any elements already in the queue that are greater than or equal to the new element can never become the “minimum value”, so we remove them from the queue. This keeps the elements in the queue in “ascending order” (from smallest to largest). - Removing old elements: When the window size exceeds \(K\), we remove elements that entered the queue \(K\) or more steps ago from the front of the queue (checking from the front). - Calculating the score: When the window size reaches \(K\), the front of the maximum queue represents the “maximum value of the current interval”, and the front of the minimum queue represents the “minimum value of the current interval”. We calculate their difference and update the maximum difference for that observation site. - After examining all intervals, if the maximum score is at least \(T\), we increment the answer by \(1\).

Complexity

• Time Complexity: \(O(N \times M)\) Since each element is added to and removed from the queues at most once, the processing for a single observation site takes \(O(M)\) time.
• Space Complexity: \(O(N \times M)\) We need memory to store the input data and the queues for the sliding window (arrays of length \(M\)). This takes \(O(N \times M + M)\) space, which simplifies to \(O(N \times M)\) complexity.

Implementation Points

• While you can use collections.deque in Python, to optimize for speed, you can simulate a deque using a custom array (list) and two pointers (left l and right r) to reduce the constant-factor overhead.

• When \(K = 1\), the maximum and minimum values within any interval are the same, so the score is always \(0\). Thus, the condition is satisfied if and only if \(T \leq 0\). Handling this case explicitly simplifies the logic.

  Source Code

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    T = int(data[3])
    
    ans = 0
    
    max_dq_buf = [0] * M
    min_dq_buf = [0] * M
    
    idx = 4
    for _ in range(N):
        A = [int(x) for x in data[idx:idx+M]]
        idx += M
        
        if K == 1:
            if 0 >= T:
                ans += 1
            continue
            
        max_score = -1
        
        max_l = 0
        max_r = 0
        min_l = 0
        min_r = 0
        
        for i in range(M):
            val = A[i]
            
            while max_r > max_l and A[max_dq_buf[max_r - 1]] <= val:
                max_r -= 1
            max_dq_buf[max_r] = i
            max_r += 1
            
            while min_r > min_l and A[min_dq_buf[min_r - 1]] >= val:
                min_r -= 1
            min_dq_buf[min_r] = i
            min_r += 1
            
            if max_dq_buf[max_l] <= i - K:
                max_l += 1
            if min_dq_buf[min_l] <= i - K:
                min_l += 1
                
            if i >= K - 1:
                diff = A[max_dq_buf[max_l]] - A[min_dq_buf[min_l]]
                if diff > max_score:
                    max_score = diff
                    
        if max_score >= T:
            ans += 1
            
    print(ans)

solve()

This editorial was generated by or-glm5.2-high.