概要

各選手からのパス先は実は高々 \(1\) 通りに決まります。
そのため、選手たちを「各頂点の出次数が \(1\) 以下のグラフ」として見て、各開始位置について「捕球されるか」「最終保持者が誰か」を高速に前計算します。

考察

まず、選手 \(i\) がパスするときの相手を考えます。

パス範囲 \([L_i, R_i]\) の中で、自分以外の最も番号が小さい選手に渡すので、

• \(L_i < i\) なら、パス先は \(L_i\)
• \(L_i = i\) かつ \(R_i > i\) なら、パス先は \(i+1\)
• \(L_i = R_i = i\) なら、パス先は存在しない

です。

したがって、各選手からのパス先は一意に決まります。
これを nxt[i] とします。パス先がない場合は nxt[i] = 0 とします。

---

素朴に各ボールについてパスをシミュレーションすると、ボールのスピード \(W_j\) は最大 \(10^9\) なので、最悪で \(10^9\) 回近いパスが起こり得ます。
\(M\) も最大 \(2 \times 10^5\) なので、これは間に合いません。

---

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

• holder[i]
  選手 \(i\) から十分速いボールを始めたとき、最終保持者になる選手
  ただし、必ずどこかで捕球される場合は \(0\)

• C[i]
  選手 \(i\) からスピード \(W\) で始めたとき、\(W \leq C[i]\) なら捕球される、というしきい値

例えば、選手 \(i\) のパス先が \(u\) だとします。

選手 \(i\) でスピード \(W\) のボールを受け取った場合、

• \(W \leq D_i\) なら、その場で捕球
• \(W > D_i\) なら、スピード \(W-1\) で \(u\) に渡る

選手 \(u\) では、スピードが \(C[u]\) 以下なら捕球されます。
つまり、選手 \(i\) から見ると、パス後に捕球される条件は

\(W - 1 \leq C[u]\)

すなわち

\(W \leq C[u] + 1\)

です。

よって、選手 \(i\) から始めたときに捕球される条件は

\(W \leq \max(D_i, C[u] + 1)\)

になります。

したがって、

\(C[i] = \max(D_i, C[u] + 1)\)

と計算できます。

---

ただし、グラフにはサイクルが存在する可能性があります。

サイクルに入ると、同じ選手を何度も訪れることがあります。
しかし、パスのたびにスピードは \(1\) ずつ減り、すべての \(D_i \geq 0\) なので、いずれスピードは \(0\) 以下になり、必ず誰かに捕球されます。

つまり、サイクルに到達する選手から始めた場合、最終保持者は存在せず、答えは必ず \(-1\) です。

アルゴリズム

まず、各選手のパス先 nxt[i] を求めます。

if L_i < i:
    nxt[i] = L_i
else if R_i > i:
    nxt[i] = i + 1
else:
    nxt[i] = 0

これで、選手を頂点、パスを辺とする関数グラフになります。

---

次に、DFS 的に各頂点を処理します。

状態 state[i] を用意します。

• 0: 未訪問
• 1: 現在探索中
• 2: 処理済み

各未訪問の頂点から nxt をたどっていきます。

サイクルを見つけた場合

探索中の頂点に再び到達したら、その部分はサイクルです。

サイクル上の頂点は、どれも最終的には必ず捕球されるので、

holder[i] = 0
C[i] = INF

とします。

ここで INF は十分大きい値です。

サイクルでない部分の処理

パス先がない頂点、つまり nxt[i] = 0 の場合、

• \(W \leq D_i\) なら捕球
• \(W > D_i\) なら、その選手が最終保持者

なので、

holder[i] = i
C[i] = D_i

です。

パス先 u = nxt[i] がすでに処理済みなら、次のように計算できます。

パス先から最終保持者が存在しない場合

holder[u] = 0 なら、選手 \(u\) 以降では必ず捕球されます。
したがって、選手 \(i\) から始めても必ず捕球されます。

holder[i] = 0
C[i] = INF

パス先から最終保持者が存在する場合

holder[u] が存在するなら、選手 \(i\) から始めた場合の最終保持者も同じです。

holder[i] = holder[u]
C[i] = max(D_i, C[u] + 1)

逆順に処理することで、常にパス先の情報が先に計算済みになります。

---

最後に各クエリ \((T, W)\) に答えます。

• holder[T] = 0 なら、必ず捕球されるので \(-1\)
• そうでなくても、\(W \leq C[T]\) なら捕球されるので \(-1\)
• それ以外なら、最終保持者は holder[T]

です。

計算量

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

各選手は高々一度だけ探索・処理されます。
各ボールへの回答は \(O(1)\) です。

実装のポイント

• パス先が存在しない場合を nxt[i] = 0 として扱うと実装しやすいです。

• サイクル検出には state 配列を使います。

• C[i] は \(D_i\) にパス回数分が加わる可能性があるため、long long を使います。

• サイクルに到達する頂点は必ず捕球されるため、holder[i] = 0 としてまとめて扱えます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<long long> D(N + 1), C(N + 1);
    vector<int> nxt(N + 1, 0), holder(N + 1, 0), state(N + 1, 0);

    for (int i = 1; i <= N; i++) {
        int L, R;
        cin >> D[i] >> L >> R;

        if (L < i) {
            nxt[i] = L;
        } else if (R > i) {
            nxt[i] = i + 1;
        } else {
            nxt[i] = 0;
        }
    }

    const long long INF = (1LL << 60);

    for (int s = 1; s <= N; s++) {
        if (state[s] != 0) continue;

        vector<int> path;
        int cur = s;

        while (cur != 0 && state[cur] == 0) {
            state[cur] = 1;
            path.push_back(cur);
            cur = nxt[cur];
        }

        int start = (int)path.size() - 1;

        if (cur != 0 && state[cur] == 1) {
            int pos = (int)path.size() - 1;
            while (path[pos] != cur) pos--;

            for (int i = pos; i < (int)path.size(); i++) {
                int v = path[i];
                holder[v] = 0;
                C[v] = INF;
                state[v] = 2;
            }

            start = pos - 1;
        }

        for (int i = start; i >= 0; i--) {
            int v = path[i];

            if (nxt[v] == 0) {
                holder[v] = v;
                C[v] = D[v];
            } else {
                int u = nxt[v];

                if (holder[u] == 0) {
                    holder[v] = 0;
                    C[v] = INF;
                } else {
                    holder[v] = holder[u];
                    C[v] = max(D[v], C[u] + 1);
                }
            }

            state[v] = 2;
        }
    }

    while (M--) {
        int T;
        long long W;
        cin >> T >> W;

        if (holder[T] == 0 || W <= C[T]) {
            cout << -1 << '\n';
        } else {
            cout << holder[T] << '\n';
        }
    }

    return 0;
}

---

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