Overview

This is a simulation problem where players standing in a line pass a ball to each other according to specific rules. For each ball, we determine whether it is eventually caught by some player, or if it stops because no further passes can be made.

By focusing on the fact that the destination of each pass is uniquely determined (Functional Graph), we can process each query quickly by combining backward BFS (Breadth-First Search) and doubling.

---

Analysis

1. Determining the Pass Destination (Uniqueness)

According to the rules, the player to whom player \(i\) passes is “the player with the smallest index, excluding themselves.” In player \(i\)’s passing range \([L_i, R_i]\), the minimum index excluding \(i\) itself, nxt[i], is uniquely determined as follows:

• When \(L_i = R_i = i\): There are no other players in the range, so they cannot pass (they will be the final holder).
• When \(L_i < i\): There is a player to their left (with a smaller index). The minimum value in the range is always \(L_i\). Therefore, the pass destination is \(L_i\).
• When \(L_i = i\) and \(R_i > i\): There are no players to their left, only to their right. The smallest index excluding themselves is \(i + 1\). Therefore, the pass destination is \(i + 1\).

In this way, the transition from each player is always uniquely determined. This means that the passing relationships among the players form a directed graph with an out-degree of 1 (a Functional Graph).

2. Introducing a Dummy Vertex and Precomputing the Final Holder

If we reach a player who cannot pass, that player becomes the “final holder”. To simplify the implementation, we introduce a dummy player \(N+1\) as the transition destination for players who cannot pass. The catching power of the dummy player \(N+1\) is set to \(-\infty\) so that they will never catch the ball.

If the ball continues to be passed without being caught, which “unable-to-pass player” it eventually reaches is uniquely determined solely by the starting position \(T_j\). Therefore, by performing a BFS traversing the reverse edges starting from the dummy vertex \(N+1\), we can precompute for all players \(u\) the “player unable to pass who is eventually reached when ignoring catching” last[u] in \(O(N)\) time.

3. Determining Whether the Ball is Caught (Doubling)

The speed of the ball decreases by \(1\) with each pass. If we start from player \(curr\) and take \(s\) steps to reach player \(v\), the condition for the ball to be caught is \(W - s \le D_v\), which is equivalent to \(W \le D_v + s\).

Simulating the process step-by-step for each query would take up to \(10^9\) steps, which would result in a Time Limit Exceeded (TLE) error. Therefore, we use doubling to quickly determine whether the ball is caught within \(2^p\) steps.

---

Algorithm

Constructing the Doubling Table

We define the following two tables:

• to_dbl[p][i]: The player reached after taking \(2^p\) steps from player \(i\).
• max_val[p][i]: The maximum value of \(D_{path[s]} + s\) during the \(2^p\) steps starting from player \(i\).

The transition formulas are as follows:

\[ \text{to\_dbl}[p][i] = \text{to\_dbl}[p-1][\text{to\_dbl}[p-1][i]] \]

\[ \text{max\_val}[p][i] = \max \left( \text{max\_val}[p-1][i], \ \text{max\_val}[p-1][\text{to\_dbl}[p-1][i]] + 2^{p-1} \right) \]

*Note: In the latter \(2^{p-1}\) steps, the number of steps from the start is offset (increased) by \(2^{p-1}\). Thus, we add \(2^{p-1}\) to the max_val of the latter part when combining them.

Processing Queries

For each ball \((T, W)\), let the current position be curr = T and the number of steps taken so far be dist = 0. We loop \(p\) from \(29\) down to \(0\).

• If \(W \le \text{max\_val}[p][curr] + \text{dist}\), the ball will be caught during these \(2^p\) steps, so we do not move.
• Otherwise, the ball will not be caught during these \(2^p\) steps, so we can safely advance. We update dist += 2^p and curr = to_dbl[p][curr].

After the loop ends, curr is at the position just before the limit of where the ball can go without being caught. Finally, we check if the ball is caught at the next step (i.e., at the current curr).

• If \(W \le D_{curr} + \text{dist}\), the ball is caught at this position, so the answer is -1.
• Otherwise, the ball can reach the unable-to-pass player without ever being caught, so the answer is the precomputed last[T].

---

Complexity

• Time Complexity: \(O((N + M) \log (\max W))\)

  • Determining transitions and backward BFS: \(O(N)\)
  • Constructing the doubling table: \(O(N \log (\max W))\)
  • Processing each query: \(O(\log (\max W))\)
  • Since \(N, M \le 2 \times 10^5\) and \(\max W \le 10^9\) (\(\log_2(10^9) \approx 30\)), this easily runs within the time limit.

• Space Complexity: \(O(N \log (\max W))\)

  • The size of the doubling table is dominant.

---

Implementation Details

• Preventing Overflow: Since the values of D[i] + dist and max_val can become large when checking the catching condition, you must use a 64-bit integer type (long long in C++) for the calculations.

• Setting up the Dummy Vertex: The catching power of the dummy vertex \(N+1\) should be set to a sufficiently small value (such as \(-10^{15}\)) to ensure it never catches the ball.

• Size of Doubling: Since \(W_j \le 10^9\), the number of doubling steps \(P = 30\) is sufficient, as \(2^{30} > 10^9\).

  Source Code

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

using namespace std;

const long long INF = 1000000000000000LL; // 10^15

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> D(N + 2);
    vector<int> L(N + 1), R(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> D[i] >> L[i] >> R[i];
    }
    // ダミー頂点 N+1 のキャッチ力は十分に小さく設定し、絶対にキャッチされないようにする
    D[N + 1] = -INF;

    // 各頂点からの遷移先を決定
    vector<int> nxt(N + 2);
    for (int i = 1; i <= N; ++i) {
        if (L[i] == i && R[i] == i) {
            nxt[i] = N + 1;
        } else if (L[i] < i) {
            nxt[i] = L[i];
        } else {
            nxt[i] = i + 1;
        }
    }
    nxt[N + 1] = N + 1;

    // 逆辺のグラフを構築
    vector<vector<int>> rev(N + 2);
    for (int i = 1; i <= N; ++i) {
        rev[nxt[i]].push_back(i);
    }

    // 各頂点から到達可能な「パス不可の頂点」を BFS で求める
    vector<int> last(N + 2, -1);
    queue<int> q;
    for (int v : rev[N + 1]) {
        if (v <= N) {
            last[v] = v;
            q.push(v);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int to : rev[u]) {
            if (to <= N && last[to] == -1) {
                last[to] = last[u];
                q.push(to);
            }
        }
    }

    // ダブリングテーブルの構築 (P = 30, 2^30 > 10^9)
    vector<vector<int>> to_dbl(30, vector<int>(N + 2));
    vector<vector<long long>> max_val(30, vector<long long>(N + 2));

    for (int i = 1; i <= N + 1; ++i) {
        to_dbl[0][i] = nxt[i];
        max_val[0][i] = D[i];
    }

    for (int p = 1; p < 30; ++p) {
        for (int i = 1; i <= N + 1; ++i) {
            to_dbl[p][i] = to_dbl[p - 1][to_dbl[p - 1][i]];
            max_val[p][i] = max(max_val[p - 1][i], max_val[p - 1][to_dbl[p - 1][i]] + (1LL << (p - 1)));
        }
    }

    // クエリ処理
    for (int j = 0; j < M; ++j) {
        int T;
        long long W;
        cin >> T >> W;

        int curr = T;
        long long dist = 0;
        for (int p = 29; p >= 0; --p) {
            if (W <= max_val[p][curr] + dist) {
                // この 2^p 歩の間にキャッチされるので、進まない
            } else {
                // 安全に進める
                dist += (1LL << p);
                curr = to_dbl[p][curr];
            }
        }

        // ループ終了時の判定
        if (W <= D[curr] + dist) {
            cout << -1 << "\n";
        } else {
            cout << last[T] << "\n";
        }
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.