Overview

First, precompute “on which day each streetlight becomes dark,” then process queries in increasing order of day \(T\), progressively activating streetlights as they become dark.
Use Union-Find to manage connected components of activated (= dark) streetlights, and efficiently update the count of dark sub-intervals.

Analysis

The straightforward approach for each query would be to check for every streetlight whether “\(C_i(T_j) \le K\),” then count the number of sub-intervals from the lengths of consecutive dark segments.
However, this results in \(O(NQ)\), which is too slow for \(N+Q \le 2\times 10^5\).

Key Observation 1: Once a streetlight becomes dark, it stays dark

The brightness is \(C_i(t)=\max(0, A_i-D_i t)\) which is monotonically non-increasing.
Therefore, “whether it is dark or not” changes from false -> true at most once over time (or stays false / stays true the entire time).

This means for each streetlight \(i\), we can precompute: - When it becomes dark (the minimum \(t\)).

From the condition \(A_i-D_i t \le K\): - If \(A_i \le K\), it is already dark at \(t=0\). - If \(A_i > K\) and \(D_i=0\), it never becomes dark. - Otherwise,
\(t \ge \dfrac{A_i-K}{D_i}\), so
the minimum integer time is
\(t_i=\left\lceil\dfrac{A_i-K}{D_i}\right\rceil =\dfrac{(A_i-K)+D_i-1}{D_i}\) (ceiling division).

Key Observation 2: Processing queries in chronological order makes it “addition-only”

If we process queries \(T_j\) in ascending order, the set of dark streetlights only grows as time progresses.
This allows us to handle “activating a streetlight when it becomes dark” as an event-based process.

Key Observation 3: The desired value can be maintained using connected component sizes

Consider an array where dark streetlights are marked as 1. The answer is
“the sum of \(\frac{m(m+1)}{2}\) over each maximal consecutive segment of 1s with length \(m\).”

When a single streetlight is activated, only its neighbors are affected, so managing connected components with Union-Find allows efficient updates.
If a component has size \(s\), its contribution is \(\frac{s(s+1)}{2}\).
When merging two components: - Subtract the two old contributions. - Add the one new contribution.
This maintains the overall value correctly.

Algorithm

1. For each streetlight \(i\), compute the “day it becomes dark” \(t_i\) and add (t_i, i) to events (skip streetlights that never become dark).
2. Store queries as (T_j, original index).
3. Sort both events and queries in ascending order of time.
4. Prepare a Union-Find and an active[i] array (whether the streetlight is dark), and maintain cur as the current number of dark sub-intervals.
5. For each query time \(T\):
   • Activate all streetlights with event.day <= T.
   • On activation:
     • Add it as a standalone component (cur += 1).
     • Union with active left and right neighbors.
     • Update using the \(\frac{s(s+1)}{2}\) difference when performing Union.
   • The current value of cur is the answer for this query.
6. Output answers in the original query order.

Complexity

• Time complexity: \(O((N+Q)\log(N+Q))\) (dominated by sorting; Union-Find is nearly linear).
• Space complexity: \(O(N+Q)\)

Implementation Notes

• Use t = (num + D - 1) / D for ceiling division (where num = A-K).

• Don’t forget to handle the case when D=0 (the streetlight may never become dark).

• The answer can become very large, so use long long.

• Check active to prevent double activation (this code includes a safety check for this).

• When merging in Union-Find, correctly implement the order of contribution updates (subtract first, then add).

  Source Code

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

struct DSU {
    int n;
    vector<int> p, sz;
    long long cur = 0; // total number of all-dark subsegments
    DSU(int n=0): n(n), p(n+1), sz(n+1,0) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x){
        while(p[x] != x){
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    void activate(int x, const vector<char>& active){
        p[x] = x;
        sz[x] = 1;
        cur += 1; // new single segment
        if(x > 1 && active[x-1]) unite(x, x-1);
        if(x < n && active[x+1]) unite(x, x+1);
    }
    void unite(int a, int b){
        a = find(a); b = find(b);
        if(a == b) return;
        if(sz[a] < sz[b]) swap(a,b);
        // remove old contributions
        cur -= 1LL * sz[a] * (sz[a] + 1) / 2;
        cur -= 1LL * sz[b] * (sz[b] + 1) / 2;
        p[b] = a;
        sz[a] += sz[b];
        // add new contribution
        cur += 1LL * sz[a] * (sz[a] + 1) / 2;
    }
};

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

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

    vector<pair<long long,int>> events; // (day when becomes dark, index)
    events.reserve(N);

    for(int i=1;i<=N;i++){
        long long A,D;
        cin >> A >> D;
        if(A <= K){
            events.push_back({0, i});
        }else{
            if(D == 0){
                // never dark
            }else{
                // need smallest t >= 0 s.t. A - D*t <= K => t >= (A-K)/D
                long long num = A - K;
                long long t = (num + D - 1) / D;
                events.push_back({t, i});
            }
        }
    }

    vector<pair<long long,int>> queries(Q); // (T, original index)
    for(int j=0;j<Q;j++){
        long long T;
        cin >> T;
        queries[j] = {T, j};
    }

    sort(events.begin(), events.end());
    sort(queries.begin(), queries.end());

    vector<long long> ans(Q, 0);
    vector<char> active(N+2, 0);
    DSU dsu(N);

    int ei = 0, E = (int)events.size();
    for(auto &qq : queries){
        long long T = qq.first;
        int qi = qq.second;
        while(ei < E && events[ei].first <= T){
            int idx = events[ei].second;
            if(!active[idx]){
                active[idx] = 1;
                dsu.activate(idx, active);
            }
            ei++;
        }
        ans[qi] = dsu.cur;
    }

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

---

This editorial was generated by gpt-5.3-codex.