Overview

Instead of directly enumerating the weight of each door at each time step, we enable fast computation of “the total number of locks on doors \(1\) through \(y\).”
Using this prefix sum, we can determine the stamina needed to move to a certain room, and then find the reachable left and right endpoints using binary search.

Analysis

Doors are numbered from \(1\) to \(L-1\), but since \(L\) can be up to \(10^9\), we cannot store the weight of each door in an array.

Instead, let’s consider which doors guard pattern \(i\) locks at a given time \(T\).

Guard pattern \(i\) locks door \(x\) when

\[ x \equiv R_i + V_iT \pmod{A_i} \]

is satisfied.

Let

\[ b_i = (R_i + V_iT) \bmod A_i \]

Since door numbers start from \(1\), the first door number \(f_i\) that gets locked is:

• When \(b_i > 0\): \(f_i = b_i\)
• When \(b_i = 0\): \(f_i = A_i\)

For example, if \(A_i=5, b_i=2\), the locked doors are

\[ 2, 7, 12, 17, \dots \]

On the other hand, if \(A_i=5, b_i=0\), the locked doors are

\[ 5, 10, 15, 20, \dots \]

In other words, the doors locked by each guard pattern form an arithmetic sequence.

---

Now, consider at time \(T\):

\[ C(y) = \text{the total weight of doors }1\text{ through }y \]

The number of locks that guard pattern \(i\) places on doors \(1\) through \(y\) is:

\[ \begin{cases} \left\lfloor \dfrac{y - f_i}{A_i} \right\rfloor + 1 & (y \geq f_i) \\ 0 & (y < f_i) \end{cases} \]

Therefore, \(C(y)\) can be computed by summing this value over all guard patterns.

---

Let’s consider the cost of moving from room \(S\) to room \(c\).

Moving to the right

When \(S \leq c\), the doors passed through are

\[ S+1, S+2, \dots, c \]

Therefore, the required stamina is

\[ C(c) - C(S) \]

Moving to the left

When \(c \leq S\), the doors passed through are

\[ c+1, c+2, \dots, S \]

Therefore, the required stamina is

\[ C(S) - C(c) \]

---

\(C(y)\) is non-decreasing as \(y\) increases.
Therefore, the reachable right and left endpoints can be found using binary search.

Naively checking each room takes \(O(L)\), and since \(L \leq 10^9\), this is too slow.
Enumerating each door is also impossible.

However, if we can compute the prefix sum \(C(y)\) in \(O(N)\), then each query can be processed in \(O(N \log L)\) using binary search.
Since the constraint guarantees \(N \times Q \leq 3 \times 10^5\), this is fast enough.

Algorithm

For each query \((T, S, P)\), do the following:

First, compute the first locked door number \(f_i\) for each guard pattern at time \(T\).

Let

\[ b_i = (R_i + V_iT) \bmod A_i \]

then

\[ f_i = \begin{cases} b_i & (b_i > 0) \\ A_i & (b_i = 0) \end{cases} \]

Next, compute the function \(C(y)\) as follows:

\[ C(y) = \sum_{i=1}^{N} \begin{cases} \left\lfloor \dfrac{y - f_i}{A_i} \right\rfloor + 1 & (y \geq f_i) \\ 0 & (y < f_i) \end{cases} \]

This represents “the total number of locks on doors \(1\) through \(y\).”

---

First, compute

\[ C(S) \]

Finding the right endpoint

The condition for reaching room \(c\) on the right side is

\[ C(c) - C(S) \leq P \]

This can be rewritten as

\[ C(c) \leq C(S) + P \]

Since \(C(c)\) is non-decreasing, we find the maximum \(c\) satisfying the condition using binary search.

If the cost to reach the rightmost room \(L-1\) is at most \(P\), the right endpoint is simply \(L-1\).

Finding the left endpoint

The condition for reaching room \(c\) on the left side is

\[ C(S) - C(c) \leq P \]

This can be rewritten as

\[ C(c) \geq C(S) - P \]

Therefore, we find the minimum \(c\) satisfying the condition using binary search.

If

\[ C(S) \leq P \]

then room \(0\) is reachable, so the left endpoint is \(0\).

---

Ultimately, the reachable rooms form a contiguous interval.

\[ [\text{left}, \text{right}] \]

Therefore, the answer is

\[ \text{right} - \text{left} + 1 \]

Complexity

• Time complexity: \(O(NQ \log L)\)
• Space complexity: \(O(N + Q)\)

For each query, computing the prefix sum \(C(y)\) takes \(O(N)\), and binary search performs \(O(\log L)\) prefix sum computations.
However, since the constraint guarantees \(N \times Q \leq 3 \times 10^5\), this is sufficiently fast.

Implementation Notes

• Note that door numbers start from \(1\), but room numbers start from \(0\).
• When \(b_i = 0\), the first locked door is \(A_i\), not \(0\).
  • Therefore, in the code we use ((R[i] + V[i] * T) % A[i]) or A[i].
• prefix_sum(y) is the total sum from door \(1\) to door \(y\).
  • In particular, prefix_sum(0) equals \(0\).
• Since the weight of each door is at most \(N\), if

\[ P \geq N \times \max(S, L-1-S) \]

then the stamina is always sufficient to reach either end, so the answer can immediately be set to \(L\).

Source Code

import sys

def prefix_sum(y, A, F, idxs):
    total = 0
    for i in idxs:
        f = F[i]
        if y >= f:
            total += (y - f) // A[i] + 1
    return total

def main():
    input = sys.stdin.buffer.readline

    N, L, Q = map(int, input().split())
    A = []
    R = []
    V = []

    for _ in range(N):
        a, r, v = map(int, input().split())
        A.append(a)
        R.append(r)
        V.append(v)

    idxs = range(N)
    F0 = [(R[i] or A[i]) for i in idxs]
    static = not any(V)

    Lm1 = L - 1
    calc = prefix_sum
    out = []

    for _ in range(Q):
        T, S, P = map(int, input().split())

        dl = S
        dr = Lm1 - S
        if P >= N * (dl if dl >= dr else dr):
            out.append(str(L))
            continue

        if static or T == 0:
            F = F0
        else:
            F = [((R[i] + V[i] * T) % A[i]) or A[i] for i in idxs]

        cs = calc(S, A, F, idxs)

        if S == Lm1:
            right = Lm1
        else:
            total = calc(Lm1, A, F, idxs)
            if total - cs <= P:
                right = Lm1
            else:
                target = cs + P
                lo, hi = S, Lm1
                while lo < hi:
                    mid = (lo + hi + 1) >> 1
                    if calc(mid, A, F, idxs) <= target:
                        lo = mid
                    else:
                        hi = mid - 1
                right = lo

        if cs <= P:
            left = 0
        else:
            target = cs - P
            lo, hi = 0, S
            while lo < hi:
                mid = (lo + hi) >> 1
                if calc(mid, A, F, idxs) >= target:
                    hi = mid
                else:
                    lo = mid + 1
            left = lo

        out.append(str(right - left + 1))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.