概要

各選手からボールのパス先が一意に決まるという性質を利用し、ダブリング（倍増法）を用いて各ボールの移動を高速にシミュレーションする問題です。

---

考察

1. パス先の一意性

各選手 \(i\) がボールをパスするとき、パス先の候補は \([L_i, R_i]\) から自分自身 \(i\) を除いた範囲で「最も番号の小さい選手」です。 制約 \(L_i \leq i \leq R_i\) より、各選手 \(i\) からのパス先 nxt[i] は以下のように一意に定まります。

1. \(L_i < i\) のとき： 自分より左側に候補が存在するため、その中で最も番号の小さい選手は \(L_i\) です。
2. \(L_i = i\) かつ \(R_i > i\) のとき： 自分より左側には候補がなく、右側にのみ存在するため、最も番号の小さい選手は \(i + 1\) です。
3. \(L_i = R_i = i\) のとき： 自分以外にパスできる選手がいないため、パス先は存在しません（選手 \(i\) が最終保持者になります）。この場合は便宜上、パス先を \(0\) とします。

このように、各選手からのパス先は \(O(1)\) で求めることができます。

2. 愚直なシミュレーションの限界

各ボールについて「キャッチされるかパス先がなくなるまで1歩ずつシミュレーションする」という素朴なアプローチを考えてみます。 この場合、ボールのスピード \(W_j\) は最大で \(10^9\) であり、パスの回数も最大で \(O(N)\) 回になる可能性があるため、1つのボールにつき最悪 \(O(N)\) の計算量がかかります。 ボールの個数 \(M\) も最大で \(2 \times 10^5\) であるため、全体の計算量は \(O(NM)\) となり、実行時間制限（TLE）になってしまいます。

3. ダブリングによる高速化

選手から選手へのパスは「出次数が1以下（遷移先が1つ以下）の有向グラフ」とみなせます。このような構造では、ダブリングを適用して「\(2^k\) 手先の遷移」を事前に計算しておくことで、シミュレーションを高速化できます。

ただし、今回は単に移動するだけでなく、「途中でキャッチされる（スピード \(W\) がその選手のキャッチ力 \(D\) 以下になる）」という条件を判定しながら進む必要があります。 そこで、ダブリングの過程で「途中でキャッチされずに進むために、出発時点で最低限必要なスピード」も同時に管理します。

---

アルゴリズム

1. ダブリングテーブルの定義

\(K = 30\)（\(2^{30} > 10^9\)）として、以下の2つのテーブルを定義します。

• to[k][i] : 選手 \(i\) から出発して \(2^k\) 回パスしたときに到達する選手（途中でパス先がなくなる場合は \(0\)）。
• max_val[k][i] : 選手 \(i\) から出発して \(2^k\) 回パスする（または途中で終了する）過程において、途中でキャッチされてしまわないために必要な、出発時点でのボールの最小スピード。
  • 出発時のボールのスピードを \(W\) としたとき、\(W \leq \text{max\_val}[k][i]\) であれば、この \(2^k\) 歩の移動の途中のどこかでキャッチされます。

2. テーブルの初期化と更新

初期値（\(k = 0\)、すなわち 1 歩の移動）

• to[0][i] = nxt[i]
• max_val[0][i] = max(D[i], D[nxt[i]] + 1)
  • 選手 \(i\) 自身でキャッチされる条件は \(W \leq D_i\) です。
  • 次の選手 nxt[i] でキャッチされる条件は、移動後のスピードについて \(W - 1 \leq D_{nxt[i]} \iff W \leq D_{nxt[i]} + 1\) です。
  • このいずれかを満たすとキャッチされるため、その最大値をとります。

遷移（\(k \to k+1\)、すなわち \(2^{k+1}\) 歩の移動）

\(2^{k+1}\) 歩の移動は、「\(i\) から \(2^k\) 歩進んで \(u = \text{to}[k][i]\) に到達し、そこからさらに \(2^k\) 歩進む」と分解できます。 * to[k+1][i] = to[k][u] * max_val[k+1][i] = max(max_val[k][i], max_val[k][u] + 2^k) * 前半の \(2^k\) 歩でキャッチされる条件は \(W \leq \text{max\_val}[k][i]\) です。 * 後半の \(2^k\) 歩でキャッチされる条件は、後半の開始時点（\(u\) に到達した時点）のスピード \(W - 2^k \leq \text{max\_val}[k][u] \iff W \leq \text{max\_val}[k][u] + 2^k\) です。

3. クエリの処理

各ボール \((T, W)\) について、以下の手順でシミュレーションを行います。

1. 初期位置での判定: もし \(W \leq D_T\) ならば、一歩も動けずにキャッチされるため、即座に -1 を出力します。
2. ダブリングによるジャンプ: \(k = 29, 28, \ldots, 0\) の順にループを回します。 もし次の移動先が存在し（to[k][curr] != 0）、かつキャッチされずに \(2^k\) 歩進める（W > max_val[k][curr]）ならば：
   • 実際に \(2^k\) 歩進めます：curr = to[k][curr] とし、スピードを W -= 2^k と減らします。
3. 最終判定: これ以上進めなくなったとき、次のパス先 to[0][curr] が \(0\)（パス先がない）であれば、curr が最終保持者となります。そうでなければ、次の1歩で必ずキャッチされるため、結果は -1 になります。

---

計算量

• 時間計算量: \(O((N + M) \log W_{\max})\)
  • ダブリングテーブルの構築に \(O(N \log W_{\max})\) かかります。
  • 各クエリの処理において、ダブリングの遷移を試すのに \(O(\log W_{\max})\) かかります。これが \(M\) クエリ分あるため、全体で \(O(M \log W_{\max})\) です。
  • \(W_{\max} \le 10^9\) より \(\log W_{\max} \approx 30\) なので、実行時間制限に十分間に合います。
• 空間計算量: \(O(N \log W_{\max})\)
  • サイズ \(30 \times (N+1)\) の二次元配列 to および max_val を保持するため、空間計算量は \(O(N \log W_{\max})\) となります。

---

実装のポイント

• 番兵の活用: パス先が存在しない状態（nxt[i] = 0）や、場外への遷移を統一的に扱うため、インデックス 0 を番兵として扱っています。D[0] = -INF と設定しておくことで、存在しない選手にパスしてキャッチされるようなバグを防ぐことができます。

• ビット演算: \(2^k\) の計算は 1 << k を用いることで、高速かつ簡潔に実装できます。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])

    D = [0] * (N + 1)
    L = [0] * (N + 1)
    R = [0] * (N + 1)

    idx = 2
    for i in range(1, N + 1):
        D[i] = int(input_data[idx])
        L[i] = int(input_data[idx + 1])
        R[i] = int(input_data[idx + 2])
        idx += 3

    nxt = [0] * (N + 1)
    for i in range(1, N + 1):
        if L[i] < i:
            nxt[i] = L[i]
        elif L[i] == i and R[i] > i:
            nxt[i] = i + 1
        else:
            nxt[i] = 0

    K = 30
    to = [[0] * (N + 1) for _ in range(K)]
    INF = 10**18
    max_val = [[-INF] * (N + 1) for _ in range(K)]

    D[0] = -INF
    to_0 = to[0]
    max_val_0 = max_val[0]
    for i in range(1, N + 1):
        nxt_i = nxt[i]
        to_0[i] = nxt_i
        val1 = D[i]
        val2 = D[nxt_i] + 1
        max_val_0[i] = val1 if val1 > val2 else val2

    to_0[0] = 0
    max_val_0[0] = -INF

    for k in range(K - 1):
        to_k = to[k]
        max_val_k = max_val[k]
        to_kp1 = to[k + 1]
        max_val_kp1 = max_val[k + 1]
        two_k = 1 << k

        for i in range(N + 1):
            u = to_k[i]
            to_kp1[i] = to_k[u]
            val1 = max_val_k[i]
            val2 = max_val_k[u] + two_k
            max_val_kp1[i] = val1 if val1 > val2 else val2

    out = []
    for _ in range(M):
        T = int(input_data[idx])
        W = int(input_data[idx + 1])
        idx += 2

        if W <= D[T]:
            out.append("-1")
            continue

        curr = T
        for k in range(K - 1, -1, -1):
            nxt_node = to[k][curr]
            if nxt_node != 0 and W > max_val[k][curr]:
                curr = nxt_node
                W -= 1 << k

        if to[0][curr] == 0:
            out.append(str(curr))
        else:
            out.append("-1")

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。