Overview

We precompute the “day each streetlight goes dark” and process the queries in increasing order of the number of days.
By adding darkened streetlights one by one, we maintain the lengths of consecutive dark segments to compute the answers.

Analysis

Whether a streetlight is dark after \(t\) days can be determined by:

\[ C_i(t) = \max(0, A_i - D_i \times t) \leq K \]

The key observation here is that since the brightness of a streetlight only decreases over time, once a streetlight becomes dark, it stays dark forever.

In other words, if we precompute the “first day each streetlight becomes dark,” then for a query \(T\), we only need to consider:

streetlights whose first day of becoming dark is at most \(T\).

---

Let \(t_i\) be the first day the \(i\)-th streetlight becomes dark.

• If \(A_i \leq K\), it is dark from the start, so \(t_i = 0\).
• If \(A_i > K\) and \(D_i = 0\), the brightness never decreases, so it never becomes dark.
• Otherwise, we need to find the smallest integer \(t\) such that:

\[ A_i - D_i \times t \leq K \]

which gives:

\[ t_i = \left\lceil \frac{A_i - K}{D_i} \right\rceil \]

In integer arithmetic, this can be computed as:

\[ t_i = \frac{A_i - K + D_i - 1}{D_i} \]

---

Next, suppose we know which streetlights are dark at a given point in time.

For example, in a segment where \(m\) consecutive streetlights are dark, the number of contiguous sub-segments that can be chosen from it is:

\[ \frac{m(m+1)}{2} \]

Therefore, the answer is:

the sum of \(\frac{m(m+1)}{2}\) over all consecutive dark segments.

---

Naively checking all streetlights for each query costs \(O(NQ)\).
Since \(N+Q \leq 2 \times 10^5\), this is too slow.

Instead, we process the queries in increasing order of the number of days.

As the number of days increases, dark streetlights only increase.
Therefore, among the streetlights not yet added, we simply add those whose day of becoming dark is at most the current query’s day.

When adding a dark streetlight, if there are already dark streetlights to its left or right, we merge them.
This “merging of consecutive segments” can be efficiently managed using Union-Find.

Algorithm

1. For each streetlight, compute the first day it becomes dark, \(t_i\).
2. Store \((t_i, i)\) as events in an array.
3. Save queries \((T_j, j)\) along with their original indices.
4. Sort events and queries each in increasing order of the number of days.
5. Prepare a Union-Find structure.
   • Track whether each streetlight is currently dark using active.
   • Manage consecutive dark segments as connected components in the Union-Find.
   • Maintain the current answer as total.
6. Process queries in increasing order of the number of days.
   • Add all streetlights whose day of becoming dark is at most \(T_j\).
   • When adding, if the left or right neighbor is dark, merge using Union-Find.
   • The current total is the answer for this query.
7. Finally, output the answers in the original query order.

---

Here is an explanation of the values managed by the Union-Find.

When there is a consecutive dark segment of length \(x\), the number of dark sub-segments that can be chosen from it is:

\[ f(x) = \frac{x(x+1)}{2} \]

When a new dark streetlight is added, a segment of length \(1\) is created first, so we add \(1\) to the answer.

If there are dark segments to the left or right, we merge them.

For example, merging a segment of length \(a\) with a segment of length \(b\) produces a segment of length \(a+b\).

The change in the answer is:

\[ -f(a) - f(b) + f(a+b) \]

In the code, this update is performed inside the unite function of the Union-Find.

Complexity

• Time complexity: \(O((N+Q)\log(N+Q))\)
  • This comes from sorting the streetlight events and queries.
  • Union-Find operations take nearly constant time.
• Space complexity: \(O(N+Q)\)

Implementation Notes

• For streetlights that never become dark, i.e., \(A_i > K\) and \(D_i = 0\), set the day to a sufficiently large value INF.

• The answer can be as large as \(O(N^2)\), so use long long.

• Queries are sorted for processing, but the output must be in the original order, so store the query indices alongside them.

• In the Union-Find, only darkened streetlights are treated as active, and merging is performed only when neighboring streetlights are active.

  Source Code

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

using ll = long long;

struct DSU {
    vector<int> parent, sz;
    vector<char> active;
    ll total = 0;

    DSU(int n) : parent(n), sz(n, 1), active(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    ll calc(ll x) {
        return x * (x + 1) / 2;
    }

    void unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;

        if (sz[ra] < sz[rb]) swap(ra, rb);

        total -= calc(sz[ra]);
        total -= calc(sz[rb]);

        parent[rb] = ra;
        sz[ra] += sz[rb];

        total += calc(sz[ra]);
    }

    void add(int x) {
        if (active[x]) return;

        active[x] = 1;
        parent[x] = x;
        sz[x] = 1;
        total += 1;

        if (x > 0 && active[x - 1]) unite(x, x - 1);
        if (x + 1 < (int)active.size() && active[x + 1]) unite(x, x + 1);
    }
};

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

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

    const ll INF = (1LL << 60);

    vector<pair<ll, int>> events;

    for (int i = 0; i < N; i++) {
        ll A, D;
        cin >> A >> D;

        ll t;
        if (A <= K) {
            t = 0;
        } else if (D == 0) {
            t = INF;
        } else {
            t = (A - K + D - 1) / D;
        }

        events.push_back({t, i});
    }

    vector<pair<ll, int>> queries(Q);
    for (int i = 0; i < Q; i++) {
        ll T;
        cin >> T;
        queries[i] = {T, i};
    }

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

    DSU dsu(N);
    vector<ll> ans(Q);

    int idx = 0;
    for (auto [T, qi] : queries) {
        while (idx < N && events[idx].first <= T) {
            dsu.add(events[idx].second);
            idx++;
        }
        ans[qi] = dsu.total;
    }

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

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.