Overview

This problem requires organizing the conditions on the initial impact value for each domino to fall normally, then combining precomputation with binary search to efficiently answer each experiment (query).

Analysis

First, let’s consider a naive approach. For each query’s initial impact value \(S\), if we simulate by computing the impact value sequentially from domino \(1\), each query takes up to \(O(N)\) time. Since there are \(Q\) queries, the total time complexity becomes \(O(NQ)\), which exceeds the time limit (TLE) under the constraints (\(N, Q \le 2 \times 10^5\)).

Instead, let’s organize mathematically “what range must the initial impact value \(S\) fall within for domino \(i\) to fall normally?”

The impact value \(C_i\) when reaching domino \(i\) equals the initial impact value \(S\) plus all the impact increments accumulated up to that point: \(C_i = S + D_1 + D_2 + \dots + D_{i-1}\)

The condition for domino \(i\) to fall normally is \(C_i \le P_i\). Substituting the above equation and solving for \(S\): \(S + D_1 + D_2 + \dots + D_{i-1} \le P_i\) \(S \le P_i - (D_1 + D_2 + \dots + D_{i-1})\)

Let us define the right-hand side as \(M_i\). That is, \(M_i = P_i - \sum_{k=1}^{i-1} D_k\). For domino \(i\) to fall normally, we need \(S \le M_i\).

Furthermore, the condition for all dominoes from domino \(1\) to domino \(i\) to fall normally is that the condition must be satisfied for every domino \(1, 2, \dots, i\), meaning \(S \le M_1, S \le M_2, \dots, S \le M_i\) must all hold simultaneously. In other words, this is equivalent to “\(S\) is at most the minimum of \(M_1\) through \(M_i\)”.

So we prepare a new array \(L\) and define \(L_i = \min(M_1, M_2, \dots, M_i)\). Then the condition for all dominoes up to domino \(i\) to fall normally can be expressed simply as \(S \le L_i\).

This array \(L\) has the property that “values monotonically decrease (or stay the same) as the index increases” (\(L_1 \ge L_2 \ge \dots \ge L_N\)). Thanks to this monotonicity, we can use binary search to find “the maximum \(i\) such that \(S \le L_i\)”, allowing each query to be processed in \(O(\log N)\).

Algorithm

1. Precomputation (Building array \(L\)):
   • Initialize a variable sum_D to \(0\) to track the cumulative sum of impact increments.
   • Set \(L_1 = P_1\).
   • For \(i = 2, 3, \dots, N\), compute the following in order:
     • Add \(D_{i-1}\) to sum_D.
     • Compute \(M_i = P_i - \text{sum\_D}\).
     • Compute \(L_i = \min(L_{i-1}, M_i)\) and store it in the array.
2. Query Processing (Binary Search):
   • For each experiment’s initial impact value \(S\), use binary search to find the maximum \(i\) satisfying \(S \le L_i\).
   • Set ok = 0 (a state that definitely satisfies the condition, or represents 0 dominoes fallen) and ng = N + 1 (a state that definitely does not satisfy the condition), then narrow down the boundary by examining the midpoint mid.
   • The final value of ok is the number of the last domino that fell normally.

Complexity

• Time complexity: \(O(N + Q \log N)\)
  • Precomputing array \(L\) takes \(O(N)\).
  • Each query requires \(O(\log N)\) for binary search, so \(Q\) queries take \(O(Q \log N)\).
  • Overall this is very fast and comfortably fits within the time limit.
• Space complexity: \(O(N + Q)\)
  • \(O(N)\) memory is used to store the domino information and array \(L\).
  • \(O(Q)\) memory is used to store the output results.

Implementation Notes

• Fast I/O: Due to large constraints and heavy input data, in Python instead of calling input() in a loop, reading all at once with sys.stdin.read().split() and outputting with sys.stdout.write() collectively can significantly reduce execution time.

• Memory-efficient cumulative sum: There is no need to maintain a separate array for the cumulative sum of \(D_i\); simply accumulating into the variable sum_D within the loop keeps both memory usage and implementation simple.

• Binary search boundary conditions: When “even domino \(1\) doesn’t fall,” the answer is \(0\). By setting the initial value of binary search to ok = 0, even when no \(i\) satisfies the condition, \(0\) is naturally output — an elegant design.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    P = [0] * (N + 1)
    D = [0] * (N + 1)
    
    idx = 2
    for i in range(1, N + 1):
        P[i] = int(input_data[idx])
        D[i] = int(input_data[idx+1])
        idx += 2
        
    S = [int(x) for x in input_data[idx:]]
    
    L = [0] * (N + 1)
    L[1] = P[1]
    sum_D = 0
    
    for i in range(2, N + 1):
        sum_D += D[i - 1]
        M_i = P[i] - sum_D
        L[i] = L[i - 1] if L[i - 1] < M_i else M_i
        
    out = []
    for s in S:
        ok = 0
        ng = N + 1
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if s <= L[mid]:
                ok = mid
            else:
                ng = mid
        out.append(str(ok))
        
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.