概要

この問題は、2つの道路における街灯の点灯状況（明るさ）を比較し、時刻 \(1\) から \(T\) までの間で、高橋君の道路の方が明るい（点灯している街灯の個数が多い）時刻の総数を求める問題です。

時刻の上限 \(T\) が最大で \(10^9\) と非常に大きいため、1時刻ずつ愚直にシミュレーションするのではなく、座標圧縮といもす法を用いて、明るさが変化するイベント時刻のみを効率的に処理することで解くことができます。

---

考察

1. 愚直なシミュレーションの限界

最も単純な方法は、時刻 \(t = 1, 2, \ldots, T\) のそれぞれについて、高橋君と青木君の街灯が何個点灯しているかを数え上げて比較することです。 しかし、制約を見ると \(T \le 10^9\) であるため、各時刻をループで処理すると実行時間制限（通常2秒）に到底間に合いません（TLEとなります）。

2. 状態が変化する「イベント」に着目する

ここで、道路の明るさが変化するタイミングについて考えてみましょう。 高橋君の \(i\) 番目の街灯は、時刻 \(A_i\) に点灯し、時刻 \(A_i + D\) に消灯します。つまり、明るさが変化するのは、各街灯が「点灯する時刻」と「消灯する時刻」のいずれかです。

これらの明るさが変化する時刻（イベント時刻）は、高橋君と青木君を合わせても高々 \(2N + 2M\) 個しかありません。\(N, M \le 2 \times 10^5\) であるため、イベント時刻は最大でも \(8 \times 10^5\) 個程度です。 イベント時刻とイベント時刻の間の期間では、道路の明るさは一切変化しません。

したがって、「イベントが発生する時刻」で数直線を区切り、各区間内での明るさをまとめて計算することで、計算量を大幅に削減できます。

---

アルゴリズム

この問題は、以下の3つのステップで解くことができます。

Step 1: イベント時刻の列挙と座標圧縮

明るさが変化する可能性のある時刻、および数え上げの境界となる時刻をすべて集めて、重複を排除した上で昇順にソートします。 集める時刻は以下の通りです。 - 高橋君の街灯の点灯・消灯時刻: \(A_i, A_i + D\) - 青木君の街灯の点灯・消灯時刻: \(B_j, B_j + D\) - 集計対象の開始・終了時刻: \(1, T + 1\)

これらをソートして重複を消した配列を \(u\) とします。\(u\) の要素数を \(K\) とすると、数直線は \([u_0, u_1), [u_1, u_2), \ldots, [u_{K-2}, u_{K-1})\) という \(K-1\) 個の半開区間に分割されます。それぞれの区間内では、明るさは一定です。

Step 2: いもす法による区間の明るさの計算

区間ごとの明るさを効率的に求めるために、いもす法（累積和による区間更新）を使用します。 サイズ \(K\) の配列 diffA と diffB を \(0\) で初期化し、各街灯の情報を元に差分を記録します。

• 高橋君の \(i\) 番目の街灯について:
  • 点灯時刻 \(A_i\) に対応するインデックスで diffA を \(+1\) する。
  • 消灯時刻 \(A_i + D\) に対応するインデックスで diffA を \(-1\) する。
• 青木君の \(j\) 番目の街灯についても同様に diffB を更新する。

元の時刻から配列 \(u\) におけるインデックスを求める際は、二分探索（std::lower_bound）を用いることで高速に行えます。

Step 3: 累積和の計算と集計

配列 \(u\) を左から走査しながら、diffA と diffB の累積和をとることで、各区間 \([u_i, u_{i+1})\) における高橋君の明るさ \(X\) と青木君の明るさ \(Y\) を求めます。

もし \(X > Y\) であれば、その区間は「高橋君の道路のほうが明るい」状態です。 この区間 \([u_i, u_{i+1})\) のうち、求めたい範囲 \([1, T+1)\) と重なる部分の長さ（時刻の個数）を答えに加算します。 重なる部分の左端は \(L = \max(u_i, 1)\)、右端は \(R = \min(u_{i+1}, T+1)\) と表され、重なりの長さは \(R - L\)（ただし \(L < R\) のとき）となります。

---

計算量

• 時間計算量: \(O((N + M) \log(N + M))\)

  • イベント時刻の列挙に \(O(N + M)\)
  • 座標圧縮のためのソートに \(O((N + M) \log(N + M))\)
  • 二分探索を用いた差分の記録に \(O((N + M) \log(N + M))\)
  • 累積和と集計に \(O(N + M)\)
  • 全体として、制約の \(N, M \le 2 \times 10^5\) に対して十分高速（100ms前後）に動作します。

• 空間計算量: \(O(N + M)\)

  • 座標圧縮した時刻を保持する配列 \(u\) や、差分配列 diffA, diffB のサイズは高々 \(2N + 2M + 2\) であり、メモリ制限に対して十分余裕があります。

---

実装のポイント

• オーバーフローの防止: \(D\) や \(T\) は最大で \(10^9\) であり、消灯時刻 \(A_i + D\) は最大で \(2 \times 10^9\) に達します。また、最終的な答え（明るい時刻の総数）は最大で \(T = 10^9\) になります。 C++ではこれらを扱うために、時刻や答えを保持する変数には long long 型を使用する必要があります。

• 半開区間の扱い: 時刻 \(t\) から持続時間 \(D\) だけ点灯する場合、点灯している時刻は \(t, t+1, \ldots, t+D-1\) の \(D\) 個です。 これを開区間・半開区間の形で表すと、\( [t, t+D)\) となり、消灯する時刻を \(t+D\) とみなすことで、区間の長さが直感的に \((t+D) - t = D\) と計算できるようになり、バグを減らすことができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<long long> B(M);
    for (int i = 0; i < M; ++i) {
        cin >> B[i];
    }

    // イベントが発生する時刻の候補を列挙
    vector<long long> u;
    u.reserve(2 * N + 2 * M + 2);
    u.push_back(1);
    u.push_back(T + 1);
    for (int i = 0; i < N; ++i) {
        u.push_back(A[i]);
        u.push_back(A[i] + D);
    }
    for (int i = 0; i < M; ++i) {
        u.push_back(B[i]);
        u.push_back(B[i] + D);
    }

    // 座標圧縮
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());

    int K = u.size();
    vector<int> diffA(K, 0);
    vector<int> diffB(K, 0);

    // いもす法のための差分更新
    for (int i = 0; i < N; ++i) {
        auto it1 = lower_bound(u.begin(), u.end(), A[i]);
        diffA[it1 - u.begin()]++;
        auto it2 = lower_bound(u.begin(), u.end(), A[i] + D);
        diffA[it2 - u.begin()]--;
    }

    for (int i = 0; i < M; ++i) {
        auto it1 = lower_bound(u.begin(), u.end(), B[i]);
        diffB[it1 - u.begin()]++;
        auto it2 = lower_bound(u.begin(), u.end(), B[i] + D);
        diffB[it2 - u.begin()]--;
    }

    long long ans = 0;
    int X = 0, Y = 0;
    // 各区間 [u[i], u[i+1]) において明るさを計算
    for (int i = 0; i + 1 < K; ++i) {
        X += diffA[i];
        Y += diffB[i];
        if (X > Y) {
            // 区間 [u[i], u[i+1]) と [1, T+1) の共通部分の長さを求める
            long long L = max(u[i], 1LL);
            long long R = min(u[i + 1], T + 1);
            if (L < R) {
                ans += R - L;
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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