\(i\) 番目のドミノが倒れることの必要十分条件は、次の \(2\) つの条件をどちらも満たすことです。

• \(i=1\) であるか、\(i-1\) 番目のドミノが倒れる。
• \(S+D _ 1+D _ 2+\cdots+D _ {i-1}\le P _ i\) である。

\(2\) つめの条件を少し変形すると \(S\le P _ i-D _ 1-D _ 2-\cdots-D _ {i-1}\) となります。 この \(P _ i-D _ 1-D _ 2-\cdots-D _ {i-1}\) を新しく \(C _ i\) とおくと、\(i\) 番目のドミノが倒れることの必要十分条件は \(\displaystyle S\le\min _ {1\le j\le i}C _ j\) となります。

すべての \(C _ i\) および \(\displaystyle\min _ {1\le j\le i}C _ j\) を求めることは \(O(N)\) 時間でできるので、求めた \(\displaystyle\min _ {1\le j\le i}C _ j\) をもとに二分探索を行うことでクエリあたり \(O(\log N)\) 時間でこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;
    int N, Q;
    cin >> N >> Q;

    vector<long> C;
    long D_prefix_sum = 0;
    for (int i = 0; i < N; ++i) {
        int P, D;
        cin >> P >> D;
        C.emplace_back(P - D_prefix_sum);
        D_prefix_sum += D;
    }
    // 先頭から累積 min を計算する
    for (int i = 1; i < N; ++i) {
        C[i] = min(C[i], C[i - 1]);
    }

    for (int i = 0; i < Q; ++i) {
        int S;
        cin >> S;
        // 二分探索で答えを求める
        cout << ranges::upper_bound(C, S, greater{}) - begin(C) << endl;
    }
    return 0;
}

from bisect import bisect_right


N, Q = map(int, input().split())

C = []
D_prefix_sum = 0
for i in range(N):
    P, D = map(int, input().split())
    C.append(P - D_prefix_sum)
    D_prefix_sum += D

# 先頭から累積 min を計算する
for i in range(1, N):
    C[i] = min(C[i], C[i - 1])

for i in range(Q):
    S = int(input())
    print(bisect_right(C, -S, key=lambda x: -x))