概要

各時刻の「高橋の点灯数 − 青木の点灯数」を考え、その値が正になる時刻（\(1 \le t \le T\)）の個数を、差分（いもす法）＋座標圧縮で高速に数えます。

考察

各街灯は、点灯操作時刻を \(s\) とすると整数時刻 \(s, s+1, \dots, s+D-1\) の間だけ点灯します。
つまり「点灯している個数」は、時刻ごとに区間の重なり数（区間加算）になっています。

素朴に時刻 \(t=1\) から \(T\) まで全て調べると、\(T\) が最大 \(10^9\) なので不可能です（\(O(T)\) で TLE）。

ここで重要な観察は次の通りです。

• 明るさ（点灯数）は、ある時刻で急に変化するのは「点灯開始時刻」や「点灯終了の次の時刻」だけ。
• それ以外の時刻では、明るさは一定。

したがって、変化が起きる時刻だけをイベントとして集め、その間の区間長をまとめて足し込めばよいです。

さらに「高橋が明るい」かどうかだけ知りたいので、両者の点灯数を別々に管理する代わりに
差 \(diff(t) = (\text{高橋の点灯数}) - (\text{青木の点灯数})\) を管理すると簡単になります。

各街灯の寄与は次の区間加算です：

• 高橋の街灯（開始 \(a\)）は \([a, a+D)\) に \(+1\)
• 青木の街灯（開始 \(b\)）は \([b, b+D)\) に \(-1\)

このとき \(diff(t) > 0\) である時刻の総数を数えれば答えです。

アルゴリズム

差分配列（いもす法）を「時刻が巨大なので辞書で」行い、変化点だけソートして走査します。

1. \(end\_cap = T+1\) とする（\([1, T]\) の整数時刻を数えるための右端番兵）。
2. 連想配列 delta を用意し、各区間 \([l, r)\) の加算 \(v\) を
   • delta[l] += v
   • delta[r] -= v で記録する。
3. 高橋の各 \(a\) について、区間は \([a, \min(a+D, T+1))\) に \(+1\)。
4. 青木の各 \(b\) について、区間は \([b, \min(b+D, T+1))\) に \(-1\)。
5. 変化点として delta のキーに加え、必ず 1 と T+1 も入れてソート（座標圧縮の役目）。
6. 昇順に変化点 pos[i] を走査し、
   • 現在の差 diff に delta[pos[i]] を加える
   • 次の変化点までの区間長は pos[i+1] - pos[i]
   • もし diff > 0 なら、その区間長を答えに加算する
7. 得られた合計が、\(1 \le t \le T\) のうち高橋の方が明るい整数時刻の個数。

※整数時刻を数えているのに「区間長」を足してよい理由：
今回の時刻は整数で、差分は半開区間 \([p, q)\)（整数 \(p, p+1, \dots, q-1\)）に一定なので、個数はちょうど \(q-p\) になります。

計算量

• 時間計算量: \(O((N+M)\log(N+M))\)（イベント数をソート）
• 空間計算量: \(O(N+M)\)（差分イベントを保持）

実装のポイント

• 点灯区間は \([s, s+D)\)（終了は \(s+D\)）として扱うと、差分処理がきれいになります（\(D\) 個の整数時刻に対応）。

• \(T\) を超える点灯は数えないので、終了点は必ず \(\min(s+D, T+1)\) に丸めます。

• 1 と T+1 を変化点に必ず入れることで、範囲端の取りこぼしを防げます。

• delta は通常の配列ではなく辞書（連想配列）にして、必要な時刻だけ保持します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, D, T = data[0], data[1], data[2], data[3]
    A = data[4:4 + N]
    B = data[4 + N:4 + N + M]

    end_cap = T + 1
    delta = {}

    def add(k, v):
        delta[k] = delta.get(k, 0) + v

    for a in A:
        add(a, 1)
        e = a + D
        if e > end_cap:
            e = end_cap
        add(e, -1)

    for b in B:
        add(b, -1)
        e = b + D
        if e > end_cap:
            e = end_cap
        add(e, 1)

    pos = list(delta.keys())
    pos.append(1)
    pos.append(end_cap)
    pos.sort()

    uniq = []
    prev = None
    for x in pos:
        if x != prev:
            uniq.append(x)
            prev = x
    pos = uniq

    diff = 0
    ans = 0
    for i in range(len(pos) - 1):
        p = pos[i]
        diff += delta.get(p, 0)
        if diff > 0:
            ans += pos[i + 1] - p

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。