Overview

This problem asks you to compare the lighting status (brightness) of streetlights on two roads and find the total number of time points from time \(1\) to \(T\) where Takahashi’s road is brighter (has more streetlights turned on).

Since the upper limit \(T\) can be as large as \(10^9\), naively simulating each time step is infeasible. Instead, we can solve this efficiently by using coordinate compression and the imos method (difference array technique) to process only the event times when brightness changes.

---

Analysis

1. Limitations of Naive Simulation

The simplest approach would be to count and compare the number of lit streetlights for Takahashi and Aoki at each time \(t = 1, 2, \ldots, T\). However, since the constraint states \(T \le 10^9\), iterating through each time step would far exceed the time limit (typically 2 seconds), resulting in TLE.

2. Focusing on “Events” Where State Changes

Let’s think about the moments when the brightness of a road changes. Takahashi’s \(i\)-th streetlight turns on at time \(A_i\) and turns off at time \(A_i + D\). In other words, brightness changes only at the “turn-on time” or “turn-off time” of each streetlight.

The total number of these event times (when brightness changes) is at most \(2N + 2M\) combining both Takahashi and Aoki. Since \(N, M \le 2 \times 10^5\), there are at most about \(8 \times 10^5\) event times. Between consecutive event times, the brightness of the roads does not change at all.

Therefore, by dividing the number line at “event times” and computing the brightness for each interval collectively, we can significantly reduce the computational cost.

---

Algorithm

This problem can be solved in the following three steps.

Step 1: Enumerate Event Times and Coordinate Compression

Collect all times where brightness might change, as well as boundary times for counting, remove duplicates, and sort them in ascending order. The times to collect are: - Turn-on/turn-off times of Takahashi’s streetlights: \(A_i, A_i + D\) - Turn-on/turn-off times of Aoki’s streetlights: \(B_j, B_j + D\) - Start/end times of the counting range: \(1, T + 1\)

Sort these and remove duplicates to form the array \(u\). Let \(K\) be the number of elements in \(u\). The number line is then divided into \(K-1\) half-open intervals: \([u_0, u_1), [u_1, u_2), \ldots, [u_{K-2}, u_{K-1})\). Within each interval, the brightness is constant.

Step 2: Computing Interval Brightness Using the Imos Method

To efficiently compute the brightness for each interval, we use the imos method (interval updates via prefix sums). Initialize arrays diffA and diffB of size \(K\) with \(0\), and record differences based on each streetlight’s information.

• For Takahashi’s \(i\)-th streetlight:
  • Add \(+1\) to diffA at the index corresponding to turn-on time \(A_i\).
  • Add \(-1\) to diffA at the index corresponding to turn-off time \(A_i + D\).
• Update diffB similarly for Aoki’s \(j\)-th streetlight.

To find the index in array \(u\) corresponding to an original time, binary search (std::lower_bound) can be used for efficiency.

Step 3: Prefix Sum Computation and Aggregation

Scan array \(u\) from left to right, computing prefix sums of diffA and diffB to obtain the brightness \(X\) for Takahashi and \(Y\) for Aoki in each interval \([u_i, u_{i+1})\).

If \(X > Y\), then in that interval “Takahashi’s road is brighter.” Add to the answer the length (number of time points) of the overlap between this interval \([u_i, u_{i+1})\) and the desired range \([1, T+1)\). The left endpoint of the overlap is \(L = \max(u_i, 1)\), the right endpoint is \(R = \min(u_{i+1}, T+1)\), and the length of the overlap is \(R - L\) (when \(L < R\)).

---

Complexity

• Time Complexity: \(O((N + M) \log(N + M))\)

  • Enumerating event times: \(O(N + M)\)
  • Sorting for coordinate compression: \(O((N + M) \log(N + M))\)
  • Recording differences using binary search: \(O((N + M) \log(N + M))\)
  • Prefix sum computation and aggregation: \(O(N + M)\)
  • Overall, this runs sufficiently fast (around 100ms) for the constraints \(N, M \le 2 \times 10^5\).

• Space Complexity: \(O(N + M)\)

  • The coordinate-compressed time array \(u\) and the difference arrays diffA, diffB have size at most \(2N + 2M + 2\), which is well within memory limits.

---

Implementation Notes

• Preventing Overflow: \(D\) and \(T\) can be as large as \(10^9\), and the turn-off time \(A_i + D\) can reach up to \(2 \times 10^9\). Additionally, the final answer (total number of bright time points) can be as large as \(T = 10^9\). In C++, variables holding times and the answer must use the long long type to handle these values.

• Handling Half-Open Intervals: When a streetlight is lit from time \(t\) for a duration of \(D\), the lit times are \(t, t+1, \ldots, t+D-1\), totaling \(D\) time points. Expressed as a half-open interval, this is \([t, t+D)\). By treating the turn-off time as \(t+D\), the interval length is intuitively computed as \((t+D) - t = D\), which helps reduce bugs.

  Source Code

#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;
}

---

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