Overview

This problem requires computing the time at which each streetlight becomes “dark,” processing queries offline in ascending order of time, and using Union-Find to manage contiguous intervals of dark streetlights to efficiently count the number of subintervals.

Analysis

Key Observation ①: The time at which each streetlight becomes dark is uniquely determined

The brightness of streetlight \(i\), \(C_i(t) = \max(0, A_i - D_i \times t)\), monotonically decreases (non-increases) over time. Therefore, there exists a threshold time \(t_i\) such that for all \(t \geq t_i\), the streetlight is always dark. This threshold time \(t_i\) can be computed as follows:

• If \(A_i \leq K\): it is dark from the start → \(t_i = 0\)
• If \(D_i = 0\) and \(A_i > K\): it never becomes dark → \(t_i = \infty\)
• Otherwise: \(t_i = \lceil (A_i - K) / D_i \rceil\)

Key Observation ②: The answer can be derived from the lengths of contiguous dark intervals

When a contiguous interval of dark streetlights has length \(m\), the number of subintervals \((l, r)\) contained in it is \(\frac{m(m+1)}{2}\). The overall answer is the sum of this value across all maximal contiguous dark intervals.

Problem with the naive approach

Scanning all streetlights for each query to count dark intervals would be \(O(NQ)\), which even with \(N + Q \leq 2 \times 10^5\) could reach approximately \(O(10^{10})\) in the worst case, resulting in TLE.

Solution: Offline processing + Union-Find

We exploit the monotonicity that as time progresses, dark streetlights only increase (never decrease). Sort the queries in ascending order of time, and add streetlights to the “dark” state in ascending order of their threshold times. By merging newly darkened streetlights with adjacent already-dark streetlights using Union-Find, we can efficiently manage the lengths of contiguous intervals.

Algorithm

1. Compute threshold times: For each streetlight \(i\), compute the threshold time \(t_i\).
2. Sort: Sort streetlights in ascending order of \(t_i\), and queries in ascending order of \(T_j\).
3. Incremental addition: Process queries from smallest to largest. For the current query time \(T_j\), activate all streetlights whose threshold time is at most \(T_j\).
4. Merging with Union-Find: When activating streetlight \(i\), if its left neighbor \(i-1\) or right neighbor \(i+1\) is already active, merge them using Union-Find. Add the difference in \(\frac{m(m+1)}{2}\) before and after merging to total.
5. Record the answer: The value of total after all additions for a query is that query’s answer.

Concrete example: When \(N=5\) and the threshold times of the streetlights are \([0, 3, 1, 3, 2]\):

Time	Newly darkened streetlights	Dark streetlight sequence (●=dark)	Contiguous intervals	Number of subintervals
0	#1	●○○○○	[1]	1
1	#3	●○●○○	[1],[1]	2
2	#5	●○●○●	[1],[1],[1]	3
3	#2, #4	●●●●●	[5]	15

Adding streetlight 2 → merges with streetlights 1 and 3 to form an interval of length 3. Adding streetlight 4 → merges with the interval containing streetlight 3 and streetlight 5 to form an interval of length 5.

Complexity

• Time complexity: \(O(N \log N + Q \log Q + N \alpha(N))\)
  • Sorting is dominant. \(\alpha(N)\) is the inverse Ackermann function (amortized cost per Union-Find operation).
• Space complexity: \(O(N + Q)\)

Implementation Notes

• When the threshold time is \(\infty\): Streetlights with \(D_i = 0\) and \(A_i > K\) never become dark, so set them to a sufficiently large value (such as \(2 \times 10^9 + 1\), exceeding the maximum possible \(T_j\)).

• Size management in Union-Find: Initialize sz to \(0\) and set it to \(1\) upon activation. This ensures correct size computation during merges.

• Incremental updates: When merging, subtract the “sum of subinterval counts of the old intervals” and add the “subinterval count of the new interval” to update the overall total in \(O(1)\).

• Ceiling division: Use \((A_i - K + D_i - 1) / D_i\) to perform ceiling division.

  Source Code

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> parent;
    vector<long long> sz;
    UnionFind(int n) : parent(n), sz(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    }
    void merge(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        parent[y] = x;
        sz[x] += sz[y];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    long long K;
    cin >> N >> Q >> K;

    vector<long long> threshold(N);
    for (int i = 0; i < N; i++) {
        long long A, D;
        cin >> A >> D;
        if (A <= K) {
            threshold[i] = 0;
        } else if (D == 0) {
            threshold[i] = 2000000001LL; // infinity
        } else {
            threshold[i] = (A - K + D - 1) / D;
        }
    }

    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return threshold[a] < threshold[b];
    });

    vector<pair<long long, int>> queries(Q);
    for (int j = 0; j < Q; j++) {
        cin >> queries[j].first;
        queries[j].second = j;
    }
    sort(queries.begin(), queries.end());

    auto countPairs = [](long long m) -> long long {
        return m * (m + 1) / 2;
    };

    vector<long long> ans(Q);
    UnionFind uf(N);
    vector<bool> active(N, false);
    long long total = 0;
    int ptr = 0;

    for (auto& [T, idx] : queries) {
        while (ptr < N && threshold[order[ptr]] <= T) {
            int i = order[ptr];
            active[i] = true;
            uf.sz[i] = 1;
            long long oldCount = 0;
            long long newSize = 1;

            if (i > 0 && active[i - 1]) {
                int root = uf.find(i - 1);
                oldCount += countPairs(uf.sz[root]);
                newSize += uf.sz[root];
                uf.merge(i, i - 1);
            }
            if (i < N - 1 && active[i + 1]) {
                int root = uf.find(i + 1);
                oldCount += countPairs(uf.sz[root]);
                newSize += uf.sz[root];
                uf.merge(i, i + 1);
            }

            total += countPairs(newSize) - oldCount;
            ptr++;
        }
        ans[idx] = total;
    }

    for (int j = 0; j < Q; j++) {
        cout << ans[j] << '\n';
    }

    return 0;
}

---

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