Overview

This problem requires determining whether each domino falls properly during a domino toppling process, and for Q experiments, finding the number of the last domino that falls properly.

Analysis

The impact value reaching each domino i can be expressed as \(C_i = S + \sum_{k=1}^{i-1} D_k\). The condition for domino i to fall properly is \(C_i \leq P_i\), i.e., \(S \leq P_i - \sum_{k=1}^{i-1} D_k\). Defining \(T_i = P_i - \sum_{k=1}^{i-1} D_k\), each experiment reduces to finding the first position where S exceeds \(T_i\).

A naive approach that checks all dominoes for each experiment results in \(O(NQ)\), which is too slow given the constraints (\(N, Q \leq 2 \times 10^5\)). Instead, we solve this efficiently by combining binary search with a segment tree.

Algorithm

1. As preprocessing, compute the prefix sum \(\text{cum\_d}[i] = \sum_{k=1}^{i-1} D_k\)
2. For each domino i, compute the threshold \(T_i = P_i - \text{cum\_d}[i]\)
3. Build a segment tree (minimum query) to efficiently retrieve the minimum value over an interval \([0, r]\)
4. For each experiment \(S_j\), perform binary search:
   • Retrieve the minimum value \(\text{min\_val}\) over the interval \([0, mid]\) using the segment tree
   • If \(S_j \leq \text{min\_val}\), then all dominoes up to mid fall properly, so extend the search range to the right
   • Otherwise, shrink to the left
5. The position low obtained from binary search is the first domino that does not fall properly (0-indexed)

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Preprocessing (prefix sum and segment tree construction): \(O(N)\)
  • Each experiment (binary search + segment tree query): \(O(\log N)\) × \(Q\)
• Space complexity: \(O(N)\)

Implementation Notes

• Be careful with indices when computing the prefix sum (cum_d[0] = 0, cum_d[1] = D₁, …)

• The segment tree should be implemented to compute minimum values

• Pay attention to the binary search termination condition (low indicates the first position of failure)

• Be careful with 0-indexed to 1-indexed conversion (output is 1-indexed, and the case low=0 requires special handling)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); Q = int(next(it))
    dominoes = []
    for i in range(N):
        p = int(next(it)); d = int(next(it))
        dominoes.append((p, d))
    
    S_list = [int(next(it)) for _ in range(Q)]
    
    # 累積和の配列を作成: cum_d[i] = D_1 + D_2 + ... + D_{i-1} (i>=1)
    cum_d = [0] * (N+1)
    for i in range(1, N):
        cum_d[i] = cum_d[i-1] + dominoes[i-1][1]
    
    # 各ドミノiに到達する衝撃値の式: C_i = S + (D_1 + D_2 + ... + D_{i-1}) = S + cum_d[i]
    # 正常に倒れる条件: S + cum_d[i] <= P_i
    # つまり、S <= P_i - cum_d[i]
    
    # 各ドミノiについて、閾値 T_i = P_i - cum_d[i] を計算
    T = [0] * N
    for i in range(N):
        T[i] = dominoes[i][0] - cum_d[i]
    
    # セグメント木（最小値）を構築
    size = 1
    while size < N:
        size *= 2
    seg = [10**18] * (2 * size)
    
    for i in range(N):
        seg[size + i] = T[i]
    for i in range(size-1, 0, -1):
        seg[i] = min(seg[2*i], seg[2*i+1])
    
    def query(l, r):
        l += size
        r += size
        res = 10**18
        while l < r:
            if l % 2 == 1:
                res = min(res, seg[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = min(res, seg[r])
            l //= 2
            r //= 2
        return res
    
    # 二分探索: 最初にS > T_iとなるiを探す
    # 正常に倒れるのは、i=0からi=k-1まで（0-indexedでk-1番目）
    # つまり、答えはk（1-indexed）になるが、k=0の場合は0を出力
    for s in S_list:
        low, high = 0, N
        while low < high:
            mid = (low + high) // 2
            min_val = query(0, mid+1)
            if s <= min_val:
                low = mid + 1
            else:
                high = mid
        # lowが最初に正常に倒れないドミノのindex（0-indexed）
        # 正常に倒れる最後のドミノはlow-1（0-indexed）なので、1-indexedではlow
        # ただし、low=0の場合はドミノ1も倒せないので0
        if low == 0:
            print(0)
        else:
            print(low)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.