Overview

Consider “Takahashi’s lit count − Aoki’s lit count” at each time step, and efficiently count the number of time steps (\(1 \le t \le T\)) where this value is positive, using a difference array (imos method) + coordinate compression.

Analysis

Each streetlight, given its activation time \(s\), is lit during integer times \(s, s+1, \dots, s+D-1\).
In other words, “the number of lit streetlights” at each time step corresponds to the overlap count of intervals (interval addition).

Naively checking every time \(t=1\) through \(T\) is impossible since \(T\) can be up to \(10^9\) (\(O(T)\) would TLE).

The key observation is as follows:

• The brightness (lit count) changes abruptly only at “lighting start times” or “the time step immediately after lighting ends.”
• At all other times, the brightness remains constant.

Therefore, we only need to collect the times where changes occur as events, and sum up the interval lengths between them.

Furthermore, since we only want to know whether “Takahashi is brighter,” instead of managing both players’ lit counts separately, it becomes simpler to manage the difference \(diff(t) = (\text{Takahashi's lit count}) - (\text{Aoki's lit count})\).

Each streetlight contributes the following interval addition:

• Takahashi’s streetlight (start \(a\)): \(+1\) on \([a, a+D)\)
• Aoki’s streetlight (start \(b\)): \(-1\) on \([b, b+D)\)

The answer is the total number of time steps where \(diff(t) > 0\).

Algorithm

We perform the difference array (imos method) “using a dictionary since times can be huge,” and sort and scan only the change points.

1. Set \(end\_cap = T+1\) (a right sentinel for counting integer times in \([1, T]\)).
2. Prepare an associative array delta, and for each interval \([l, r)\) addition of value \(v\), record:
   • delta[l] += v
   • delta[r] -= v
3. For each of Takahashi’s \(a\): add \(+1\) to the interval \([a, \min(a+D, T+1))\).
4. For each of Aoki’s \(b\): add \(-1\) to the interval \([b, \min(b+D, T+1))\).
5. In addition to the keys of delta, always include 1 and T+1 as change points, then sort (serving as coordinate compression).
6. Scan the change points pos[i] in ascending order:
   • Add delta[pos[i]] to the current difference diff
   • The interval length to the next change point is pos[i+1] - pos[i]
   • If diff > 0, add that interval length to the answer
7. The resulting total is the number of integer times in \(1 \le t \le T\) where Takahashi is brighter.

※ Why we can add “interval lengths” even though we’re counting integer times:
Since times are integers and the difference is constant over the half-open interval \([p, q)\) (integers \(p, p+1, \dots, q-1\)), the count is exactly \(q-p\).

Complexity

• Time complexity: \(O((N+M)\log(N+M))\) (sorting the events)
• Space complexity: \(O(N+M)\) (storing the difference events)

Implementation Notes

• Treating the lit interval as \([s, s+D)\) (ending at \(s+D\)) makes the difference processing clean (corresponding to \(D\) integer time steps).

• Since lighting beyond \(T\) should not be counted, always clamp the endpoint to \(\min(s+D, T+1)\).

• Always including 1 and T+1 as change points prevents missing the boundary of the range.

• Use a dictionary (associative array) instead of a regular array for delta, storing only the necessary time steps.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.