各観測地点について以下を求めればよいです。

• 「長さ \(M\) の配列からとれるすべての長さ \(K\) の連続部分列の max − min 」の max

以下では、\(A := S_i\) として、観測地点ごとの問題を考えます。

静的な（変更のない）列 \(A\) に対する、区間 max/min クエリが \(M - K + 1\) 回と考えれば、 Segment tree や (Disjoint) Sparse Table などのデータ構造をもちいることで \(O(M \log M)\) で解く事ができます。これらはこの問題の制約下で十分高速で AC が得られるでしょう。

今回のクエリの特徴として、クエリ区間 \([l, r]\) が \(l\) に対しても \(r\) に対しても単調である事が挙げられます。このようなクエリの特徴を活かしたデータ構造として SWAG と呼ばれるものもあります。これは（基本的に）「結合則を満たす二項演算」であれば扱うことができます。今回の問題であれば、この SWAG を用いて \(O(M)\) 解くこともできます。

さらに良い性質を要求するものとして「単調キュー」を用いた解法があります。クエリの単調性に加えて二項演算としては「 max/min 」が主な適用範囲ですが、単純なアルゴリズムで「ヒストグラム内の最大長方形」等にも応用できます。

ここでは単調キューを用いた \(O(M)\) 解法を紹介します。以下は max を求める事を考えていますが、同様に min も求められます。

空の deque を用意します。これは、常に単調減少となるようにします。

• \(A_r\) を追加するとき

  後ろから \(A_r\) 以下の値を削除し、 \(A_r\) を追加する。\(r\) を \(1\) ふやす。

• \(A_l\) を削除するとき

  先頭が \(A_l\) であるなら削除する。そうでないなら何もしない。 \(l\) を \(1\) ふやす。

すると、deque の先頭が常に区間 \([l, r]\) の最大値になります。これは、区間内の最大値がどの瞬間でも deque に含まれることから確認できます。

計算量は追加回数から削除回数も抑えられて、全体で \(O(M)\) となります。

よって問題全体を \(O(NM)\) で解けます。

実装例

from collections import deque

n, m, k, t = map(int, input().split())

ans = 0

for _ in range(n):
    a = list(map(int, input().split()))
    
    mx = deque()
    mn = deque()
    ok = False

    for i in range(m):
        while mx and a[mx[-1]] <= a[i]:
            mx.pop()
        mx.append(i)

        while mn and a[mn[-1]] >= a[i]:
            mn.pop()
        mn.append(i)

        while mx and mx[0] <= i - k:
            mx.popleft()
        while mn and mn[0] <= i - k:
            mn.popleft()
        
        if i >= k - 1:
            if a[mx[0]] - a[mn[0]] >= t:
                ok = True
                break

    ans += ok

print(ans)