Overview

This problem requires managing the number of lit streetlights on Takahashi’s and Aoki’s roads respectively, and finding the total length of time during which “Takahashi’s road is brighter (has strictly more lit streetlights)” among times from \(1\) to \(T\).

By using event sorting (sweep line method), which focuses only on the “times when the state changes” (i.e., when streetlights turn on or off), we can solve this efficiently even for the large time limit \(T \le 10^9\).

---

Key Observations

Naive Approach and Its Limitations

The simplest method is to count how many streetlights are lit for Takahashi and Aoki at each time \(1, 2, \ldots, T\). However, the upper limit \(T\) can be up to \(10^9\), and the number of streetlights \(N, M\) can be up to \(2 \times 10^5\). Naively checking each time step results in \(O(T(N+M))\) or \(O(T)\) time complexity, which exceeds the time limit (TLE).

Key Insight: Introducing Event Sorting

The brightness of the roads changes only at the following two types of moments: 1. The moment a streetlight turns on (time \(A_i\) or \(B_j\)) 2. The moment a streetlight turns off (time \(A_i + D\) or \(B_j + D\), which is \(D\) time units after turning on)

At all other times, the brightness of the roads remains constant. Therefore, by registering the times when brightness changes as “events”, sorting them chronologically, and processing them in order, we can collectively compute the intervals between consecutive events all at once.

---

Algorithm

1. Defining Events

For each streetlight of Takahashi and Aoki, we create the following events. Since we don’t need to consider times exceeding \(T\), we clip the turn-off time to \(\min(\text{turn-off time}, T + 1)\).

• Takahashi’s streetlight \(i\) (turns on at \(A_i\), lit duration \(D\))
  • At time \(A_i\), an event that increases Takahashi’s brightness by \(+1\)
  • At time \(\min(A_i + D, T + 1)\), an event that decreases Takahashi’s brightness by \(-1\)
• Aoki’s streetlight \(j\) (turns on at \(B_j\), lit duration \(D\))
  • At time \(B_j\), an event that increases Aoki’s brightness by \(+1\)
  • At time \(\min(B_j + D, T + 1)\), an event that decreases Aoki’s brightness by \(-1\)

Additionally, to correctly tally the state up to time \(T\), we add a dummy event at time \(T+1\) with no change (brightness impact of \(0\)).

2. Sorting Events

Sort all created events in ascending order of their occurrence time.

3. Simulation via Sweep Line

Initialize Takahashi’s current brightness \(H\) and Aoki’s current brightness \(A_{val}\) to \(0\), and set the previous event time \(t_{prev}\) to \(1\). Process the sorted events chronologically. When multiple events occur at the same time, process them together (using Python’s groupby, for example).

When reaching a new event time \(t\), perform the following steps:

1. Accumulate the interval: Consider the interval from the previous event time \(t_{prev}\) to just before the current event \(t - 1\) (length \(t - t_{prev}\)). The brightness does not change within this interval. If \(H > A_{val}\) (Takahashi’s road is brighter), add the length of this interval \(t - t_{prev}\) to the answer.
2. Update the state: Apply all brightness changes (\(+1\) or \(-1\)) at time \(t\) to \(H\) and \(A_{val}\).
3. Update the time: Update \(t_{prev}\) to \(t\) for processing the next event.

By repeating this process until the last event, we correctly obtain the total time during which Takahashi’s road is brighter.

---

Complexity

• Time Complexity: \(O((N+M) \log (N+M))\) The total number of events is at most \(2(N+M) + 1\). The bottleneck of the algorithm is sorting the events, which takes \(O((N+M) \log (N+M))\) time. The sweep processing after sorting runs in \(O(N+M)\), so the overall algorithm is sufficiently fast.

• Space Complexity: \(O(N+M)\) The size of the list storing events is \(O(N+M)\).

---

Implementation Notes

• Aggregating events at the same time: It is possible for “turn on” and “turn off” events to exist simultaneously at the same time. If these are processed individually, there may be a momentary incorrect brightness state (underestimation or overestimation), leading to errors in the tally. Therefore, events at the same time must always be processed collectively using tools like itertools.groupby, updating the state before computing the next time interval.

• Role of the dummy event: A dummy event is inserted at time \(T+1\) to ensure the state is fully tallied up to time \(T\). This ensures that the period from the last actual event to time \(T\) is also correctly added to the answer through step 1’s “interval accumulation”.

  Source Code

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()

---

This editorial was generated by gemini-3.5-flash-thinking.