ある時点における高橋君の道路と青木君の道路の明るさの差 \(D\) を、高橋君の道路で点灯している街灯の本数から青木君の道路で点灯している街灯の本数を引いたものとして定めます。 求めるものは、\(D\gt0\) であるような整数の時刻 \(t\ (1\le t\le T)\) の個数です。

次の \(2\) 種類の出来事を考えます。

• 時刻 \(t\) に \(D\) が \(1\) 増加する（高橋君の道路で街灯が点灯するか、青木君の道路で街灯が消える）。
• 時刻 \(t\) に \(D\) が \(1\) 減少する（高橋君の道路で街灯が消えるか、青木君の道路で街灯が点灯する）。

これらの出来事を \(t\) の昇順にソートし、\(D\) の値を管理しながら出来事を処理していくことでこの問題を解くことができます。

\(D\gt0\) かどうかが入れ替わる時刻を記録してそれぞれの区間の長さを合計してもよいですし、出来事を走査するときに同時に答えを計算してもかまいません。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M, D, T;
    cin >> N >> M >> D >> T;

    // 出来事の (時刻, D の変化) の組
    vector<pair<int, int>> event;
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        event.emplace_back(A, 1);
        event.emplace_back(min(T + 1, A + D), -1);
    }
    for (int i = 0; i < M; ++i) {
        int B;
        cin >> B;
        event.emplace_back(B, -1);
        event.emplace_back(min(T + 1, B + D), 1);
    }

    // 時刻の昇順にソート
    ranges::sort(event);

    // 求める時刻の個数, 現在の明るさの差
    int ans = 0, D = 0;
    for (auto [time, type] : event) {
        if (type > 0 && D == 0) { // 新しく D > 0 になるなら
            ans -= time; // ans を更新
        }
        if (type < 0 && D == 1) { // 新しく D <= 0 になるなら
            ans += time; // ans を更新
        }
        D += type;
    }
    cout << ans << endl;
    return 0;
}

N, M, D, T = map(int, input().split())

# 出来事の (時刻, D の変化) の組
event = []
for A in map(int, input().split()):
    event.append((A, 1))
    event.append((min(T + 1, A + D), -1))
for B in map(int, input().split()):
    event.append((B, -1))
    event.append((min(T + 1, B + D), 1))

# 時刻の昇順にソート
event.sort()

# 求める時刻の個数
ans = 0
# 現在の明るさの差
D = 0
for time, type in event:
    if type > 0 and D == 0: # 新しく D > 0 になるなら
        ans -= time # ans を更新
    if type < 0 and D == 1: # 新しく D <= 0 になるなら
        ans += time # ans を更新
    D += type

print(ans)