Overview

For each experiment’s initial shock value \(S\), we need to efficiently determine “how many dominoes from the left fall without breaking.” We transform the conditions to precompute “the upper bound that \(S\) must satisfy,” then answer each query with binary search.

Analysis

Key Insight: All conditions can be reduced to comparisons with \(S\)

The shock value reaching domino \(i\) is: - \(C_1 = S\) - \(C_{i} = S + (D_1 + D_2 + \cdots + D_{i-1})\)

Since the condition for domino \(i\) to fall normally is \(C_i \le P_i\): [ S + \sum_{k=1}^{i-1} D_k \le P_i ] [ S \le Pi - \sum{k=1}^{i-1} D_k ]

In other words, for “all dominoes up to domino \(i\) to fall,” the following must hold for all \(1 \le k \le i\): [ S \le \left(Pk - \sum{t=1}^{k-1} Dt\right) ] Therefore, domino \(i\) can be reached if and only if: [ S \le \min{1 \le k \le i}\left(Pk - \sum{t=1}^{k-1} D_t\right) ]

Why the naive solution is too slow

Simulating dominoes one by one for each query takes \(O(N)\) in the worst case. With \(Q\) queries, the total is \(O(NQ)\), which at maximum constraints becomes \(2\times 10^5 \times 2\times 10^5\) — far too slow.

Solution: Precomputation + Binary Search

If we precompute the “upper bound on \(S\) for dominoes up to \(i\) to fall” as an array, each query can find “the maximum \(i\) satisfying the condition” via binary search.

Algorithm

1. Precomputation (building array \(B\))

Define the condition for domino \(i\) as: [ T_i = Pi - \sum{k=1}^{i-1} Dk ] where $\sum{k=1}^{i-1} D_k\( is the prefix sum of increments up to just before \)i$.

Then define: [ B_i = \min(T_1, T_2, \dots, T_i) ] This represents “the maximum value of \(S\) (upper bound) needed to knock down all dominoes up to domino \(i\).”

The condition for dominoes up to \(i\) to fall is simply: [ S \le B_i ]

In implementation, we iterate from left to right maintaining a prefix sum pref = D_1 + ... + D_{i-1}: - a = P_i - pref (this is \(T_i\)) - cur_min = min(cur_min, a) (this is \(B_i\))

to build \(B\).

Since \(B_i\) is a “running minimum,” it is monotonically non-increasing (stays the same or decreases). Therefore, the set of \(i\) satisfying \(S \le B_i\) forms a contiguous interval from the beginning, making binary search applicable.

2. Processing each query (binary search)

• If \(B_1 < S\) (in code, B[0] < S), then even domino 1 doesn’t fall, so the answer is \(0\).
• Otherwise, find the maximum \(i\) such that \(B_i \ge S\) using binary search, and the answer is that \(i\) (1-indexed).

Complexity

• Time complexity: Precomputation \(O(N)\), binary search per query \(O(\log N)\), giving an overall \(O(N + Q\log N)\)
• Space complexity: \(O(N)\) for array \(B\), etc.

Implementation Notes

• \(C_i\) and prefix sums can be as large as \(S + \sum D\), so while Python handles this automatically, other languages require 64-bit integers (long long, etc.).

• Since \(B\) is monotonically non-increasing, the binary search takes the form “if \(B[m] \ge S\), move right (aim for a larger \(i\)).”

• Since the input is large, reading all at once with sys.stdin.buffer.read() improves speed.

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    Q = next(it)

    B = [0] * N
    pref = 0
    cur_min = 10**30  # sufficiently large
    for i in range(N):
        P = next(it)
        D = next(it)
        a = P - pref
        if a < cur_min:
            cur_min = a
        B[i] = cur_min
        pref += D

    out_lines = []
    for _ in range(Q):
        S = next(it)
        if B[0] < S:
            out_lines.append("0")
            continue
        l, r = 0, N - 1
        while l < r:
            m = (l + r + 1) // 2
            if B[m] >= S:
                l = m
            else:
                r = m - 1
        out_lines.append(str(l + 1))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.