Overview

If a player fails to catch the ball, the next player they pass to is uniquely determined.
Therefore, we can model this as a graph where players are vertices and passes are directed edges. For each starting position, we precompute “up to what speed the ball will be caught along the way.”

Analysis

First, let us consider the pass destination when player \(i\) fails to catch the ball.

The pass range is \([L_i, R_i]\), and the ball is passed to the player with the smallest index in this range, excluding player \(i\) themselves.

• If \(L_i < i\):
  Since there are players to the left of player \(i\) within the range, the player with the smallest index is \(L_i\).
• If \(L_i = i\) and \(R_i > i\):
  There is no player to the left, and the smallest index to the right is \(i+1\).
• If \(L_i = R_i = i\):
  There is no other player to pass to, so this player can be the final holder.

In other words, there is at most \(1\) pass destination for each player when they fail to catch.
This forms a directed graph where the out-degree of each vertex is at most \(1\), which is known as a functional graph.

If we naively simulate the passing process for each ball, since the maximum speed \(W_j\) can be up to \(10^9\), a cycle can lead to an extremely large number of passes, causing a TLE.

Therefore, we precompute the following information for each player \(i\):

• \(\mathrm{val}[i]\)
  The threshold speed such that if we start from player \(i\) with speed \(W\), the ball will be caught somewhere along the way if \(W \leq \mathrm{val}[i]\).
• \(\mathrm{holder}[i]\)
  The final holder reached when \(W > \mathrm{val}[i]\).

Note that if the ball enters a cycle instead of reaching a final holder, its speed decreases by \(1\) with each pass and eventually becomes \(0\).
Since \(D_i \geq 0\) for all \(i\), the ball will definitely be caught somewhere in this case.
Thus, the answer for such starting players is always \(-1\).

Next, we perform DP in the reverse direction starting from the players who can be final holders (i.e., players with \(L_i = R_i = i\)).

Suppose player \(u\) passes to player \(v\) when they fail to catch.
Assume we have already computed \(\mathrm{val}[v]\) for player \(v\).

When a ball with speed \(W\) arrives at player \(u\):

• If \(W \leq D_u\), player \(u\) catches it.
• If \(W > D_u\), the ball is passed to player \(v\) with speed \(W-1\).
  • The condition for the ball to be caught after this is \(W-1 \leq \mathrm{val}[v]\).
  • This is equivalent to \(W \leq \mathrm{val}[v]+1\).

Therefore, the condition for the ball to be caught starting from player \(u\) is:

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

Thus, we have:

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

Also, the final holder when starting with a sufficiently large speed is the same as when starting from player \(v\), so:

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

Algorithm

1. For each player \(i\), find the pass destination \(\mathrm{nxt}[i]\) when they fail to catch.

   • If \(L_i < i\), then \(\mathrm{nxt}[i] = L_i\).
   • Otherwise, if \(R_i > i\), then \(\mathrm{nxt}[i] = i+1\).
   • Otherwise, there is no pass destination.

2. If a pass destination exists, add \(i\) to rev[nxt[i]] as a reversed edge.

3. Players with no pass destination can be final holders, so initialize their values:

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

4. Push these players into a stack and perform a reverse DFS/BFS.

   • Let \(v\) be the current player.
   • For each player \(u\) who passes to \(v\):

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

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

1. Answer each query \((T_j, W_j)\):
   • If \(\mathrm{holder}[T_j] = 0\):
     The ball does not reach a final holder (it enters a cycle) and is always caught. The answer is \(-1\).
   • If \(W_j \leq \mathrm{val}[T_j]\):
     The ball is caught along the way. The answer is \(-1\).
   • Otherwise:
     The final holder is \(\mathrm{holder}[T_j]\).

Complexity

• Time Complexity: \(O(N+M)\)
• Space Complexity: \(O(N)\)

Implementation Details

Finding the pass destination is a key part of the implementation.

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

The case where \(nxt = 0\) represents players who have no pass destination.

Also, since each player has at most one pass destination, tracing backwards from the final holders forms a tree-like structure (a forest).
Therefore, it is sufficient to process each player at most once in the reverse DP.

Players in cycle components that do not reach any final holder will remain with holder[i] == 0.
Balls starting from such players will keep losing speed and will eventually be caught, so the answer for them is always \(-1\).

Source Code

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()

---

This editorial was generated by gpt-5.5-high.