概要

各選手がキャッチできなかったときのパス先は一意に決まります。
そのため、選手を頂点、パス先を辺とするグラフを考え、各開始位置について「どの速さまでなら途中でキャッチされるか」を前計算します。

考察

まず、選手 \(i\) がキャッチできなかった場合のパス先を考えます。

パス範囲は \([L_i, R_i]\) で、選手 \(i\) 自身を除いた中で最も番号が小さい選手に渡します。

• \(L_i < i\) の場合
  範囲内に自分より左の選手がいるので、最も番号が小さいのは \(L_i\) です。
• \(L_i = i\) かつ \(R_i > i\) の場合
  左側には誰もおらず、右側の最小は \(i+1\) です。
• \(L_i = R_i = i\) の場合
  自分以外に渡せる相手がいないので、ここが最終保持者になり得ます。

つまり、キャッチできなかったときのパス先は高々 \(1\) つです。
これは各頂点の出次数が高々 \(1\) の有向グラフ、いわゆる functional graph になります。

素朴に各ボールについて実際にパスをシミュレーションすると、スピード \(W_j\) が最大 \(10^9\) なので、サイクルに入った場合などに非常に多くの回数パスが発生し、TLE します。

そこで、各選手 \(i\) について次の情報を前計算します。

• \(\mathrm{val}[i]\)
  選手 \(i\) からスピード \(W\) で始めたとき、\(W \leq \mathrm{val}[i]\) ならどこかでキャッチされる、というしきい値
• \(\mathrm{holder}[i]\)
  \(W > \mathrm{val}[i]\) の場合に到達する最終保持者

ただし、最終保持者に到達せずサイクルに入る場合は、スピードがパスのたびに \(1\) 減り、いずれ \(0\) になります。
すべての \(D_i \geq 0\) なので、その場合は必ずどこかでキャッチされます。
したがって、そのような選手については常に答えは \(-1\) です。

次に、最終保持者になり得る選手、つまり \(L_i=R_i=i\) の選手から逆向きに DP します。

選手 \(u\) がキャッチできなかったとき、選手 \(v\) にパスするとします。
すでに \(v\) について \(\mathrm{val}[v]\) が分かっているとします。

選手 \(u\) にスピード \(W\) のボールが来たとき、

• \(W \leq D_u\) なら選手 \(u\) がキャッチする
• \(W > D_u\) なら選手 \(v\) にスピード \(W-1\) で渡る
  • その後キャッチされる条件は \(W-1 \leq \mathrm{val}[v]\)
  • つまり \(W \leq \mathrm{val}[v]+1\)

したがって、選手 \(u\) から始めてキャッチされる条件は

\[ W \leq \max(D_u, \mathrm{val}[v]+1) \]

です。

よって、

\[ \mathrm{val}[u] = \max(D_u, \mathrm{val}[v]+1) \]

となります。
また、十分大きいスピードで始めた場合の最終保持者は、選手 \(v\) から始めた場合と同じなので、

\[ \mathrm{holder}[u] = \mathrm{holder}[v] \]

です。

アルゴリズム

1. 各選手 \(i\) について、キャッチできなかったときのパス先 \(\mathrm{nxt}[i]\) を求める。

   • \(L_i < i\) なら \(\mathrm{nxt}[i] = L_i\)
   • そうでなく \(R_i > i\) なら \(\mathrm{nxt}[i] = i+1\)
   • それ以外ならパス先なし

2. パス先がある場合、逆向きの辺として rev[nxt[i]] に \(i\) を追加する。

3. パス先がない選手は最終保持者になり得るので、初期値を設定する。

   • \(\mathrm{val}[i] = D_i\)
   • \(\mathrm{holder}[i] = i\)

4. それらの選手をスタックに入れ、逆向きに DFS/BFS する。

   • 現在の選手を \(v\) とする
   • \(v\) にパスする選手 \(u\) について、

\[ \mathrm{val}[u] = \max(D_u, \mathrm{val}[v]+1) \]

\[ \mathrm{holder}[u] = \mathrm{holder}[v] \]

1. 各クエリ \((T_j, W_j)\) に答える。
   • \(\mathrm{holder}[T_j] = 0\) の場合
     最終保持者に到達しないので、必ずキャッチされる。答えは \(-1\)
   • \(W_j \leq \mathrm{val}[T_j]\) の場合
     途中でキャッチされる。答えは \(-1\)
   • それ以外の場合
     最終保持者は \(\mathrm{holder}[T_j]\)

計算量

• 時間計算量: \(O(N+M)\)
• 空間計算量: \(O(N)\)

実装のポイント

パス先を求める部分が重要です。

if l < i:
    nxt = l
elif r > i:
    nxt = i + 1
else:
    nxt = 0

\(nxt=0\) の場合は、パス先が存在しない選手です。

また、各選手のパス先は高々 \(1\) つなので、最終保持者から逆向きにたどると木のような構造になります。
そのため、逆向き DP で各選手を高々 \(1\) 回処理すれば十分です。

最終保持者に到達しないサイクル部分の選手は holder[i] == 0 のまま残ります。
そのような選手から始めたボールは、スピードが減り続けて必ずキャッチされるため、答えは常に \(-1\) になります。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

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

    D = [0] * (N + 1)
    rev = [[] for _ in range(N + 1)]
    terminals = []

    for i in range(1, N + 1):
        d, l, r = map(int, input().split())
        D[i] = d

        if l < i:
            nxt = l
        elif r > i:
            nxt = i + 1
        else:
            nxt = 0

        if nxt == 0:
            terminals.append(i)
        else:
            rev[nxt].append(i)

    val = [-1] * (N + 1)
    holder = [0] * (N + 1)

    stack = terminals[:]
    for t in terminals:
        val[t] = D[t]
        holder[t] = t

    while stack:
        v = stack.pop()
        nv = val[v] + 1
        hv = holder[v]
        for u in rev[v]:
            val[u] = D[u] if D[u] > nv else nv
            holder[u] = hv
            stack.append(u)

    ans = []
    for _ in range(M):
        t, w = map(int, input().split())
        if holder[t] == 0 or w <= val[t]:
            ans.append("-1")
        else:
            ans.append(str(holder[t]))

    print("\n".join(ans))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。