Overview

We precompute the day each streetlight becomes “dark” and process queries in increasing order of days.
While managing the process of dark streetlights being added one by one, we efficiently update the count of dark sub-intervals.

Analysis

The brightness of the \(i\)-th streetlight after \(t\) days is

\(C_i(t) = \max(0,\ A_i - D_i \times t)\)

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,” we can process queries in ascending order of days and add dark streetlights incrementally.

---

The condition for streetlight \(i\) to become dark is

\(C_i(t) \leq K\)

Since \(K \geq 0\), when \(A_i > K\) and \(D_i > 0\), we need to find the smallest \(t\) such that

\(A_i - D_i \times t \leq K\)

which gives

\(t = \left\lceil \frac{A_i - K}{D_i} \right\rceil\)

On the other hand:

• If \(A_i \leq K\), it is dark from the start, so \(t = 0\)
• If \(A_i > K\) and \(D_i = 0\), it never becomes dark

---

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

Instead, we manage the days when streetlights become dark as events, and also sort the queries by day.
Then, for each query, we process all unprocessed events whose day is at most the query’s day.

---

Next, let’s consider how to update the count of dark sub-intervals.

When there are \(m\) consecutive dark streetlights, the number of sub-intervals that can be chosen from them is

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

For example, for a consecutive dark segment of length \(3\):

• \(3\) intervals of length \(1\)
• \(2\) intervals of length \(2\)
• \(1\) interval of length \(3\)

giving a total of \(6 = \frac{3 \times 4}{2}\).

---

Suppose the streetlight at position \(x\) newly becomes dark.

Consider the case where there is a consecutive dark segment of length \(L\) to its left and a consecutive dark segment of length \(R\) to its right.

Before the addition, the left and right are separate segments.

[dark segment length L]  x  [dark segment length R]

When position \(x\) becomes dark, these merge into a single dark segment of length \(L + 1 + R\).

The number of newly added dark sub-intervals is

\((L+1)(R+1)\)

The reason is that every newly added interval must contain position \(x\).
The left endpoint can be chosen from the \(L\) streetlights on the left or \(x\) itself, giving \(L+1\) choices.
The right endpoint can be chosen from the \(R\) streetlights on the right or \(x\) itself, giving \(R+1\) choices.

Therefore, each time we add a streetlight, we simply increase the answer by

\((L+1)(R+1)\)

Algorithm

1. For each streetlight, compute the day it becomes dark:

   • If \(A_i \leq K\), then day \(0\)
   • If \(A_i > K\) and \(D_i > 0\), then \(\left\lceil \frac{A_i - K}{D_i} \right\rceil\)
   • If \(A_i > K\) and \(D_i = 0\), it never becomes dark, so ignore it

2. Store “day it becomes dark” and “streetlight position” as events in an array

3. Sort events in ascending order of day

4. Sort queries as \((T_j, j)\) in ascending order of day

   • \(j\) is the original query index
   • This is needed to output answers in the original order

5. Maintain the current count of dark sub-intervals as total

6. For each query \(T\):

   • Process all events whose day is at most \(T\)
   • Add streetlight \(x\) to the dark state
   • Check the lengths of adjacent consecutive dark segments on the left and right
   • Update with total += (left_len + 1) * (right_len + 1)
   • Record the length of the merged segment

7. The current total is the answer for query \(T\)

---

In the code, whether a streetlight is dark is managed by active.

The lengths of consecutive segments are stored in seg_len.
However, it is not necessary to store the length at every position — we only store the length at both endpoints of each segment.

For example, if a dark segment of length \(4\) spans positions \(2\) through \(5\):

Position:  0 1 2 3 4 5 6
active:    0 0 1 1 1 1 0
seg_len:   0 0 4 0 0 4 0

Only the left and right endpoints store the length \(4\).

When adding a new position \(x\):

• If the left neighbor \(x-1\) is dark, it is the right endpoint of the left segment, so the length can be obtained from seg_len[x-1]
• If the right neighbor \(x+1\) is dark, it is the left endpoint of the right segment, so the length can be obtained from seg_len[x+1]

This is how the mechanism works.

Complexity

• Time complexity: \(O((N+Q)\log(N+Q))\)
• Space complexity: \(O(N+Q)\)

Sorting the events and queries takes \(O((N+Q)\log(N+Q))\).
Each streetlight is added at most once, so the total update cost is \(O(N)\).

Implementation Notes

When computing the day a streetlight becomes dark, we use ceiling division.

\(\left\lceil \frac{A_i - K}{D_i} \right\rceil\)

can be written in integer arithmetic as

(A - K + D - 1) // D

Also, the answer can become quite large, so 64-bit integers are required.
In Python, integers have arbitrary precision, so there is no need to worry about this.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0

    N = data[idx]
    Q = data[idx + 1]
    K = data[idx + 2]
    idx += 3

    events = []

    for i in range(N):
        A = data[idx]
        D = data[idx + 1]
        idx += 2

        if A <= K:
            events.append((0, i))
        elif D > 0:
            t = (A - K + D - 1) // D
            events.append((t, i))

    queries = []
    for j in range(Q):
        T = data[idx]
        idx += 1
        queries.append((T, j))

    events.sort()
    queries.sort()

    active = bytearray(N)
    seg_len = [0] * N
    ans = [0] * Q

    total = 0
    e = 0
    m = len(events)

    for T, qi in queries:
        while e < m and events[e][0] <= T:
            x = events[e][1]
            e += 1

            left_len = 0
            right_len = 0

            if x > 0 and active[x - 1]:
                left_len = seg_len[x - 1]
            if x + 1 < N and active[x + 1]:
                right_len = seg_len[x + 1]

            total += (left_len + 1) * (right_len + 1)

            new_len = left_len + right_len + 1
            seg_len[x - left_len] = new_len
            seg_len[x + right_len] = new_len
            active[x] = 1

        ans[qi] = total

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.