Overview

This problem involves hitting a row of dominoes with a ball at an initial impact value \(S\), where the impact increases as it propagates through the dominoes. For each query, we need to efficiently determine up to which domino falls normally.

Analysis

Focusing on Cumulative Impact Values

Let’s organize the impact value \(C_i\) that reaches domino \(i\) (1-indexed).

• \(C_1 = S\)
• \(C_2 = S + D_1\)
• \(C_3 = S + D_1 + D_2\)
• In general, \(C_i = S + \sum_{k=1}^{i-1} D_k\)

Defining \(\text{prefD}[i] = D_1 + D_2 + \cdots + D_{i-1}\) (with \(\text{prefD}[1] = 0\)), we get \(C_i = S + \text{prefD}[i]\).

Transforming the Condition for Falling Normally

The condition for domino \(i\) to fall normally is \(C_i \leq P_i\), that is:

\[S + \text{prefD}[i] \leq P_i \iff S \leq P_i - \text{prefD}[i]\]

We define \(\text{threshold}[i] = P_i - \text{prefD}[i]\). Then \(\text{threshold}[i]\) is the upper bound on \(S\) for domino \(i\) to fall normally.

Finding the “Last Domino That Fell Normally”

The key point is that if domino \(k\) is shattered, the impact does not propagate to any subsequent dominoes. Therefore, the condition for all dominoes \(1, 2, \ldots, i\) to fall normally is:

\[S \leq \text{threshold}[1] \text{ and } S \leq \text{threshold}[2] \text{ and } \cdots \text{ and } S \leq \text{threshold}[i]\]

This is equivalent to \(S \leq \min(\text{threshold}[1], \ldots, \text{threshold}[i])\).

So we precompute the prefix minimum \(\text{minThresh}[i] = \min(\text{threshold}[1], \ldots, \text{threshold}[i])\). By definition, \(\text{minThresh}\) is monotonically non-increasing.

Problem with the Naive Approach

Simulating domino by domino for each query takes \(O(N)\), resulting in \(O(NQ)\) overall, which causes TLE when both \(N\) and \(Q\) are \(2 \times 10^5\).

Speeding Up with Binary Search

Since \(\text{minThresh}\) is monotonically non-increasing, for a given \(S\), we can find “the largest \(i\) such that \(S \leq \text{minThresh}[i]\)” using binary search in \(O(\log N)\).

Algorithm

1. Preprocessing: Compute the prefix sum \(\text{prefD}[i]\) of \(D\).
2. Threshold Computation: Compute \(\text{threshold}[i] = P_i - \text{prefD}[i]\).
3. Prefix Minimum: Compute \(\text{minThresh}[i] = \min(\text{minThresh}[i-1], \text{threshold}[i])\).
4. Query Processing: Since \(\text{minThresh}\) is monotonically non-increasing, \(-\text{minThresh}\) is monotonically non-decreasing. Using Python’s bisect_right, we find the number of elements where \(-\text{minThresh}[i] \leq -S\), which gives the number of dominoes that fell normally (= the answer).

Concrete Example: For \(N=3\), \(P = [5, 3, 10]\), \(D = [2, 1, 0]\), \(S = 2\):

• \(\text{prefD} = [0, 2, 3]\), \(\text{threshold} = [5, 1, 7]\), \(\text{minThresh} = [5, 1, 1]\)
• \(S=2\): \(\text{minThresh}[1]=5 \geq 2\) ✓, \(\text{minThresh}[2]=1 < 2\) ✗ → Answer is \(1\)

Complexity

• Time complexity: \(O(N + Q \log N)\) (\(O(N)\) for preprocessing, \(O(\log N)\) per query for binary search)
• Space complexity: \(O(N)\)

Implementation Notes

• \(\text{threshold}[i] = P_i - \text{prefD}[i]\) can become negative, so be careful. It works correctly even when negative.

• Python’s bisect module only works on monotonically non-decreasing sequences, so we negate \(\text{minThresh}\) to convert it into a non-decreasing sequence before applying bisect_right.

• Impact values can reach approximately \(10^9 + (2 \times 10^5) \times 10^9\), but since Python uses arbitrary-precision integers, there is no concern about overflow. In C++ and similar languages, long long must be used.

  Source Code

import sys
import bisect

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    P = [0] * N
    D = [0] * N
    for i in range(N):
        P[i] = int(input_data[idx]); idx += 1
        D[i] = int(input_data[idx]); idx += 1
    
    # For domino i, the cumulative衝撃 at domino i is S + sum(D[0..i-1])
    # Let prefix_D[i] = D[0] + D[1] + ... + D[i-1] (prefix_D[0] = 0)
    # So C_i = S + prefix_D[i]
    # Domino i is okay if C_i <= P[i], i.e., S <= P[i] - prefix_D[i]
    # 
    # Define threshold[i] = P[i] - prefix_D[i]
    # Domino i falls normally iff S <= threshold[i]
    # 
    # We need the last domino that falls normally, i.e., the largest i such that
    # all dominoes 1..i have S <= threshold[k] for k=1..i.
    # Because if domino k is crushed (S > threshold[k]), then domino k+1 never receives impact.
    # So the answer is: the largest i such that S <= min(threshold[1], threshold[2], ..., threshold[i])
    # Or equivalently, the largest i such that S <= min_threshold_prefix[i]
    # where min_threshold_prefix[i] = min(threshold[0], threshold[1], ..., threshold[i])
    # (using 0-indexed)
    
    # Compute prefix sums of D
    prefix_D = [0] * (N + 1)
    for i in range(N):
        prefix_D[i + 1] = prefix_D[i] + D[i]
    
    # threshold[i] = P[i] - prefix_D[i] for i in 0..N-1
    # min_threshold_prefix[i] = min(threshold[0..i])
    min_thresh = [0] * N
    min_thresh[0] = P[0]  # prefix_D[0] = 0
    for i in range(1, N):
        thresh_i = P[i] - prefix_D[i]
        min_thresh[i] = min(min_thresh[i - 1], thresh_i)
    
    # min_thresh is non-increasing (since we take running minimum)
    # For a given S, we need the largest i (0-indexed) such that S <= min_thresh[i]
    # Since min_thresh is non-increasing, we can binary search.
    # Answer (1-indexed) = number of dominoes that fall = (largest 0-indexed i with S <= min_thresh[i]) + 1
    # If S > min_thresh[0] (= P[0]), answer is 0.
    # If S <= min_thresh[N-1], answer is N.
    
    # min_thresh is non-increasing, so we want the rightmost position where min_thresh[i] >= S
    # Equivalently, using bisect on the negated array (which would be non-decreasing)
    # Or we can use bisect_left on -min_thresh for -S
    
    # Let's create neg_min_thresh which is non-decreasing
    neg_min_thresh = [-min_thresh[i] for i in range(N)]
    # neg_min_thresh is non-decreasing
    # We want largest i with min_thresh[i] >= S, i.e., -min_thresh[i] <= -S
    # Number of elements with -min_thresh[i] <= -S is bisect_right(neg_min_thresh, -S)
    # That gives us the count, and the answer is that count (since 0-indexed count = 1-indexed last index)
    
    out = []
    for _ in range(Q):
        S = int(input_data[idx]); idx += 1
        # bisect_right finds first index where neg_min_thresh[i] > -S
        # All indices before that have neg_min_thresh[i] <= -S, meaning min_thresh[i] >= S
        ans = bisect.bisect_right(neg_min_thresh, -S)
        out.append(str(ans))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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