Overview

This problem requires comparing the difference in brightness between two roads’ streetlights at each time step, and counting the number of times from time \(1\) to \(T\) where Takahashi’s road is brighter. We solve it efficiently by combining an event-based imos method (difference array) with coordinate compression.

Analysis

Problem with the Naive Approach

If we naively compute the brightness for each time \(t = 1, 2, \ldots, T\), the complexity becomes \(O(T \times (N + M))\). Since \(T\) can be up to \(10^9\), checking each time step one by one is far too slow.

Key Insight

A streetlight turned on at time \(A_i\) contributes \(+1\) to brightness only during times \(A_i, A_i+1, \ldots, A_i+D-1\).

If we consider the difference \(\text{diff}(t) = \text{brightness\_A}(t) - \text{brightness\_B}(t)\): - Each \(A_i\) contributes \(+1\) to diff over the interval \([A_i,\ A_i + D - 1]\) - Each \(B_j\) contributes \(-1\) to diff over the interval \([B_j,\ B_j + D - 1]\)

The diff value only changes at the start of each interval and the time step after the end of each interval. In other words, there are at most \(2(N+M)\) change points (events). Between consecutive events, diff remains constant, so we can compute the contribution of each such interval all at once using its length.

Algorithm

1. Event Generation: Using the imos method concept.

   • For each \(A_i\): \(+1\) at time \(A_i\), \(-1\) at time \(A_i + D\) (diff increases → returns to original)
   • For each \(B_j\): \(-1\) at time \(B_j\), \(+1\) at time \(B_j + D\) (diff decreases → returns to original)
   • Events beyond time \(T\) are unnecessary

2. Sort events by time

3. Sweep line processing: Scan from time \(1\) to \(T\)

   • Maintain the current diff value current_diff
   • In the interval \([\text{prev\_t},\ \text{et} - 1]\) between two consecutive event times, diff is constant
   • If current_diff > 0, add the length of that interval to the answer
   • At each event time, add the event value to current_diff to update it

4. Process the interval \([\text{prev\_t},\ T]\) after the last event similarly

Concrete Example

When \(N=1, M=1, D=3, T=10, A=[2], B=[4]\): - \(A_1=2\): \(+1\) at time 2, \(-1\) at time 5 - \(B_1=4\): \(-1\) at time 4, \(+1\) at time 7

Interval	diff	Is Takahashi’s brighter?
\([1, 1]\)	0	No
\([2, 3]\)	1	Yes (2 time steps)
\([4, 4]\)	0	No
\([5, 6]\)	-1	No
\([7, 10]\)	0	No

Answer: 2

Complexity

• Time complexity: \(O((N + M) \log(N + M))\) (dominated by sorting events)
• Space complexity: \(O(N + M)\) (for storing events)

Implementation Notes

• Do not register events whose time exceeds \(T\) (since we only consider the interval \([1, T]\))

• Note that the length of the interval \([\text{prev\_t},\ \text{et} - 1]\) is \(\text{et} - \text{prev\_t}\) (number of integer time steps)

• When multiple events occur at the same time, sum them together (manage with a dictionary)

• If the first event is after time 1, the interval \([1, \text{first event time}-1]\) has diff = 0, so it is automatically not counted

  Source Code

import sys
from itertools import accumulate

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    # For each street light activated at time t, it is on during [t, t+D-1].
    # We need brightness_A(t) > brightness_B(t) for integer t in [1, T].
    
    # brightness_A(t) = number of A_i such that A_i <= t <= A_i + D - 1
    #                  = number of A_i such that t - D + 1 <= A_i <= t
    
    # diff(t) = brightness_A(t) - brightness_B(t)
    # We need to count integer t in [1, T] where diff(t) > 0.
    
    # Each A_i contributes +1 to diff for t in [A_i, min(A_i + D - 1, T)]
    # Each B_j contributes -1 to diff for t in [B_j, min(B_j + D - 1, T)]
    
    # We use coordinate compression with events.
    # Event: at time t, diff changes. We track intervals where diff is constant.
    
    # For A_i: +1 at t=A_i, -1 at t=A_i+D (if A_i+D <= T, otherwise no end event within [1,T])
    # For B_j: -1 at t=B_j, +1 at t=B_j+D
    
    events = {}
    
    def add_event(t, val):
        if t in events:
            events[t] += val
        else:
            events[t] = val
    
    for a in A:
        start = a
        end = a + D  # diff decreases by 1 at this time
        if start <= T:
            add_event(start, 1)
            if end <= T:
                add_event(end, -1)
    
    for b in B:
        start = b
        end = b + D
        if start <= T:
            add_event(start, -1)
            if end <= T:
                add_event(end, 1)
    
    if not events:
        print(0)
        return
    
    # Sort events by time
    sorted_times = sorted(events.keys())
    
    # We need to process intervals [1, T] of integer times.
    # Between consecutive event times, diff is constant.
    # Event times are where diff changes (prefix sum of events).
    
    # We process segments: [prev_time, next_event_time - 1] with current diff value,
    # then at next_event_time, diff changes.
    
    ans = 0
    current_diff = 0
    prev_t = 1  # start of current segment
    
    for et in sorted_times:
        if et > T:
            break
        # Segment [prev_t, et - 1] has current_diff
        if et > prev_t:
            seg_len = et - prev_t  # number of integer times in [prev_t, et-1]
            if current_diff > 0:
                ans += seg_len
        # Apply event at et
        current_diff += events[et]
        prev_t = et
    
    # Remaining segment [prev_t, T]
    if prev_t <= T:
        seg_len = T - prev_t + 1
        if current_diff > 0:
            ans += seg_len
    
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.