概要

この問題は、高橋君と青木君の道路でそれぞれ点灯している街灯の数を管理し、時刻 \(1\) 以上 \(T\) 以下のうち「高橋君の道路のほうが明るい（点灯している街灯の数が真に多い）」時間の長さを求める問題です。

街灯の点灯・消灯という「状態が変化する時刻」のみに着目するイベントソート（走査線法）を用いることで、広大な時間制限 \(T \le 10^9\) に対しても高速に解くことができます。

---

考察

素朴なアプローチとその限界

最も単純な方法は、時刻 \(1, 2, \ldots, T\) のそれぞれについて、高橋君と青木君の街灯がいくつ点灯しているかをカウントすることです。 しかし、考慮する時刻の上限 \(T\) は最大で \(10^9\) であり、街灯の数 \(N, M\) も最大で \(2 \times 10^5\) です。各時刻について愚直に判定を行うと \(O(T(N+M))\) や \(O(T)\) の計算量となり、実行時間制限に間に合いません（TLE）。

重要な気づき：イベントソートの導入

街灯の明るさが変化するのは、以下の \(2\) つの瞬間だけです。 1. 街灯が点灯した瞬間（時刻 \(A_i\) または \(B_j\)） 2. 街灯が消灯した瞬間（点灯から \(D\) 時間が経過した時刻 \(A_i + D\) または \(B_j + D\)）

これら以外の時刻では、道路の明るさは変化せず一定に保たれます。 したがって、明るさが変化する時刻を「イベント」として登録し、時系列順にソートして処理していくことで、イベントとイベントの間の区間をまとめて一気に計算することができます。

---

アルゴリズム

1. イベントの定義

高橋君と青木君のそれぞれの街灯について、以下のイベントを作成します。時刻が \(T\) を超える部分は考慮する必要がないため、消灯時刻は \(\min(\text{消灯時刻}, T + 1)\) としてクリップします。

• 高橋君の街灯 \(i\) (点灯開始 \(A_i\), 点灯期間 \(D\))
  • 時刻 \(A_i\) に、高橋君の明るさを \(+1\) するイベント
  • 時刻 \(\min(A_i + D, T + 1)\) に、高橋君の明るさを \(-1\) するイベント
• 青木君の街灯 \(j\) (点灯開始 \(B_j\), 点灯期間 \(D\))
  • 時刻 \(B_j\) に、青木君の明るさを \(+1\) するイベント
  • 時刻 \(\min(B_j + D, T + 1)\) に、青木君の明るさを \(-1\) するイベント

また、時刻 \(T\) までの状態を正しく集計し終えるために、時刻 \(T+1\) に「変化なし（明るさへの影響が \(0\)）」のダミーイベントを追加しておきます。

2. イベントのソート

作成したすべてのイベントを、発生時刻の昇順でソートします。

3. 走査線（スイープライン）によるシミュレーション

現在の高橋君の明るさ \(H\)、青木君の明るさ \(A_{val}\) を \(0\) で初期化し、前回のイベント時刻 \(t_{prev}\) を \(1\) とします。 ソートされたイベントを時系列順に見ていきます。同じ時刻に複数のイベントがある場合は、それらをまとめて処理します（Pythonの groupby などを使用）。

新しいイベント時刻 \(t\) に到達したとき、以下の手順を行います。

1. 期間の集計: 直前のイベント時刻 \(t_{prev}\) から、現在のイベントの直前 \(t - 1\) までの区間（長さ \(t - t_{prev}\)）について考えます。 この区間内では明るさは変化しません。もし \(H > A_{val}\)（高橋君のほうが明るい）であれば、この期間の長さ \(t - t_{prev}\) を答えに加算します。
2. 状態の更新: 時刻 \(t\) におけるすべての明るさの変化（\(+1\) や \(-1\)）を \(H\) と \(A_{val}\) に適用します。
3. 時刻の更新: 次のイベント処理のために、 \(t_{prev}\) を \(t\) に更新します。

この処理を最後のイベントまで繰り返すことで、高橋君の道路が明るい時刻の総数が正しく求まります。

---

計算量

• 時間計算量: \(O((N+M) \log (N+M))\) イベントの総数は高々 \(2(N+M) + 1\) 個です。アルゴリズムのボトルネックはイベントのソートであり、これに \(O((N+M) \log (N+M))\) の時間がかかります。ソート後の走査処理は \(O(N+M)\) で行えるため、全体として十分高速に動作します。

• 空間計算量: \(O(N+M)\) イベントを格納するリストのサイズは \(O(N+M)\) です。

---

実装のポイント

• 同一時刻のイベントの集約: 同じ時刻に「点灯」と「消灯」のイベントが同時に存在することがあります。これらを個別に処理すると、一瞬だけ明るさが正しくない状態（過小評価や過大評価）が生まれ、集計に誤りが生じる可能性があります。そのため、同じ時刻のイベントは itertools.groupby などを用いて必ず一括で処理し、状態を更新してから次の時間経過を計算するようにします。

• ダミーイベントの役割: 時刻 \(T\) までの状態を漏れなく集計するため、時刻 \(T+1\) にダミーイベントを挿入しています。これにより、最後の実質的なイベントから時刻 \(T\) までの期間も、ステップ 1 の「期間の集計」によって正しく答えに加算されます。

  ソースコード

import sys
from itertools import groupby


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    M = int(input_data[1])
    D = int(input_data[2])
    T = int(input_data[3])

    A = [int(x) for x in input_data[4 : 4 + N]]
    B = [int(x) for x in input_data[4 + N : 4 + N + M]]

    events = []
    # 高橋君のイベント
    for a in A:
        events.append((a, 1, 0))
        events.append((min(a + D, T + 1), -1, 0))
    # 青木君のイベント
    for b in B:
        events.append((b, 0, 1))
        events.append((min(b + D, T + 1), 0, -1))
    # ダミーイベント
    events.append((T + 1, 0, 0))

    events.sort(key=lambda x: x[0])

    H = 0
    A_val = 0
    ans = 0
    t_prev = 1

    for t, g in groupby(events, key=lambda x: x[0]):
        if H > A_val:
            if t > t_prev:
                ans += t - t_prev
        dH = 0
        dA = 0
        for _, dh, da in g:
            dH += dh
            dA += da
        H += dH
        A_val += dA
        t_prev = t

    print(ans)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。