概要

\(N\) 人の選手が一列に並んでおり、各選手は決められた範囲内の最も番号の小さい選手へボールをパスします。ボールはスピードが \(1\) 減るごとにパス先を辿り、誰かのキャッチ力を下回ればキャッチされ、パス先が無ければそこで停止します。各ボールが最終的にキャッチされるか、誰の手元に残るかを求める問題です。

考察

素朴にシミュレーションを行うと、ボールのスピード \(W\) が最大 \(10^9\) であるため、最悪の場合 \(O(W)\) 回のパスが発生しTLE（実行時間超過）となります。

パスの遷移を観察すると、各選手 \(i\) のパス先は常に \(L_i\)（\(L_i < i\) の場合）または \(i+1\)（それ以外の場合）のいずれか一方に固定されています。つまり、各選手からのパス先は一意に定まり、遷移グラフは木のようになります（ただし、矢印が逆になる可能性があります）。

そこで、ダブリング（バイナリリフティング）を用いて、パスを高速にスキップすることを考えます。各選手 \(i\) について、以下の情報を事前計算しておきます： - nxt[i]: 選手 \(i\) が次にパスする選手（\(L_i = R_i = i\) の場合は自分自身） - isolated[i]: 選手 \(i\) が自分以外にパスできないかどうかのフラグ

ダブリングでは、\(2^k\) 回パスを繰り返した際の情報を管理します： - up[k][i]: \(i\) から \(2^k\) 回パスした先の選手 - hiso[k][i]: \(i\) から \(2^k\) 回進む間に、孤立した選手（パス先が自分自身の選手）を通るかどうかのフラグ - Mx[k][i]: \(i\) から \(2^k\) 回進む間に通る選手たちの「キャッチ力 \(+1\) + その選手に到達するまでのステップ数」の最大値

ここで Mx[k][i] を求めるため、Mx[0][i] は次の選手 nxt[i] のキャッチ力に \(1\) を足したもの D[nxt[i]] + 1 とします。\(k\) 段目の更新では、前半 \(2^{k-1}\) ステップと後半 \(2^{k-1}\) ステップに分け、後半部分では到達するまでに時間がかかるため、後半の最大値に \(2^{k-1}\) を足したものと前半の最大値を比較します。

ボールの処理では、現在の選手 pos と現在までに消費したスピード p を管理します。残りのスピードは \(W - p\) です。\(k\) を大きい方から順に試し、以下の2つの条件をともに満たす場合に \(2^k\) 回分のパスを一気にスキップします： 1. hiso[k][pos] が \(0\)（途中で孤立した選手を踏まない） 2. Mx[k][pos] < W - p（\(2^k\) 回進む間に誰にもキャッチされない）

これを繰り返し、スキップできなくなった地点の次の選手（nxt[pos]）でキャッチされるか孤立するかを判定して出力します。

アルゴリズム

1. 各選手のパス先 nxt[i] と孤立フラグ isolated[i] を設定する。
2. ダブリングのテーブル（up, Mx, hiso）を構築する。
3. 各ボールについて：
   • 初期位置 pos = T で、初期スピード \(W \le D[pos]\) または isolated[pos] なら即座に結果を出力。
   • そうでなければ \(k\) を大きい方からループし、条件を満たす間 pos を \(2^k\) 進め、消費スピード p に \(2^k\) を加算。
   • 最後に npos = nxt[pos] に進んだと仮定し、残りスピード W - p - 1 が D[npos] 以下ならキャッチ（\(-1\)）、そうでなければ npos が最終保持者として出力。

計算量

• 時間計算量: \(O((N + M) \log(\max W))\)
• 空間計算量: \(O(N \log(\max W))\) （\(\max W \le 10^9\) なので、\(\log(\max W) \approx 31\)）

実装のポイント

• Mx の遷移において、「現在の残りスピード」と「途中のノードのキャッチ力」を正しく比較するため、現在の位置からの相対ステップ数を加味した D[ni] + 1 をベースに計算する必要があります。

• 条件判定 Mx[k][pos] < W - p により、これから進もうとしている \(2^k\) ステップの間で一度もスピードがキャッチ力を下回らない（キャッチされない）ことを保証しています。

• 入力が大きいため、Pythonでは sys.stdin.buffer.read().split() で高速な入力読み込みを行うことが必須です。

  ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    D = [0] * (N + 1)
    isolated = [0] * (N + 1)
    nxt = [0] * (N + 1)
    for i in range(1, N + 1):
        d = int(data[idx]); idx += 1
        l = int(data[idx]); idx += 1
        r = int(data[idx]); idx += 1
        D[i] = d
        if l == i == r:
            isolated[i] = 1
            nxt[i] = i
        else:
            nxt[i] = l if l < i else i + 1

    LOG = 31
    up = [None] * LOG
    Mx = [None] * LOG
    hiso = [None] * LOG

    up[0] = nxt[:]
    Mx[0] = [0] * (N + 1)
    hiso[0] = [0] * (N + 1)
    for i in range(1, N + 1):
        ni = nxt[i]
        Mx[0][i] = D[ni] + 1
        hiso[0][i] = isolated[ni]

    for k in range(1, LOG):
        up_prev = up[k - 1]
        Mx_prev = Mx[k - 1]
        hiso_prev = hiso[k - 1]
        up_k = [0] * (N + 1)
        Mx_k = [0] * (N + 1)
        hiso_k = [0] * (N + 1)
        half = 1 << (k - 1)
        for i in range(1, N + 1):
            mid = up_prev[i]
            up_k[i] = up_prev[mid]
            a = Mx_prev[i]
            b = Mx_prev[mid] + half
            Mx_k[i] = a if a >= b else b
            hiso_k[i] = hiso_prev[i] | hiso_prev[mid]
        up[k] = up_k
        Mx[k] = Mx_k
        hiso[k] = hiso_k

    out = []
    for _ in range(M):
        T = int(data[idx]); idx += 1
        W = int(data[idx]); idx += 1
        pos = T
        if W <= D[pos] or isolated[pos]:
            out.append("-1" if W <= D[pos] else str(pos))
            continue
        p = 0
        for k in range(LOG - 1, -1, -1):
            if not hiso[k][pos] and Mx[k][pos] < W - p:
                pos = up[k][pos]
                p += (1 << k)
        npos = nxt[pos]
        remW = W - p - 1
        out.append("-1" if remW <= D[npos] else str(npos))

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

solve()

この解説は or-glm5.2-high によって生成されました。