Overview

We fix the weight of doors at the time \(T_j\) for each query and find the number of rooms reachable from room \(S_j\) with stamina at most \(P_j\).

Directly enumerating doors is impossible since \(L\) can be up to \(10^9\). Instead, we use the “prefix sum of door weights from the left end to each room” and determine the range of reachable rooms using binary search.

Analysis

We fix time \(T\) and consider the problem.

The doors locked by security pattern \(i\) are those satisfying:

\[ x \equiv R_i + V_i T \pmod{A_i} \]

Here, let:

\[ r_i = (R_i + V_i T) \bmod A_i \]

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

• When \(r_i \neq 0\): door \(r_i\)
• When \(r_i = 0\): door \(A_i\)

In other words, if we let the first door be \(\mathrm{first}_i\), then the locked doors form an arithmetic sequence:

\[ \mathrm{first}_i,\ \mathrm{first}_i + A_i,\ \mathrm{first}_i + 2A_i,\ \dots \]

For example, if \(A_i = 3,\ r_i = 2\), the locked doors are:

\[ 2, 5, 8, 11, \dots \]

---

Next, we define the function \(F(p)\) as follows:

\[ F(p) = \text{total weight of doors from door }1\text{ to door }p \]

In other words, this is the total weight of doors passed through when moving from room \(0\) to room \(p\).

The number of doors locked by pattern \(i\) among doors \(1\) through \(p\) is:

\[ \begin{cases} 0 & (p < \mathrm{first}_i) \\ \left\lfloor \dfrac{p - \mathrm{first}_i}{A_i} \right\rfloor + 1 & (p \geq \mathrm{first}_i) \end{cases} \]

By summing this over all patterns, we can compute \(F(p)\).

---

Now consider the stamina consumed when moving from room \(S\) to room \(c\).

• When \(c > S\), the doors passed through are \(S+1, S+2, \dots, c\), so the stamina consumed is:

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

• When \(c < S\), the doors passed through are \(c+1, c+2, \dots, S\), so the stamina consumed is:

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

Therefore, in both cases the stamina consumed is:

\[ |F(c) - F(S)| \]

Thus, the condition for reaching room \(c\) is:

\[ |F(c) - F(S)| \leq P \]

This is equivalent to:

\[ F(S) - P \leq F(c) \leq F(S) + P \]

Here, \(F(c)\) never decreases as \(c\) increases, i.e., it is monotonically non-decreasing.

Therefore, the rooms \(c\) satisfying the condition form a contiguous interval.
We can find the left and right endpoints of this interval using binary search.

Naively examining each room or door would be too slow since \(L\) can be up to \(10^9\), but with this method, we only need \(\log L\) operations with respect to \(L\).

Algorithm

For each query, do the following:

1. Compute the first door \(\mathrm{first}_i\) for each security pattern at time \(T\).

$\( r_i = (R_i + V_i T) \bmod A_i \)$

Then:

$\( \mathrm{first}_i = \begin{cases} A_i & (r_i = 0) \\ r_i & (r_i \neq 0) \end{cases} \)$

1. Set up the ability to compute the function \(F(p)\).

In the code, prefix_sum(pos) computes \(F(pos)\).

1. For the current position \(S\), compute:

$\( center = F(S) \)$

1. A reachable room \(c\) satisfies:

$\( center - P \leq F(c) \leq center + P \)$

So we find:

• left: the first room satisfying \(F(c) \geq center - P\)
• right: the last room satisfying \(F(c) \leq center + P\)

each using binary search.

1. The answer is:

$\( right - left + 1 \)$

Complexity

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

For each query, computing \(F(p)\) takes \(O(N)\).
Binary search calls \(F(p)\) \(O(\log L)\) times, so each query takes \(O(N \log L)\).

Since the constraints guarantee \(N \times Q \leq 3 \times 10^5\), this runs sufficiently fast.

Implementation Notes

• Since door numbers start from \(1\), the first door when the remainder is \(0\) is \(A_i\), not \(0\).

  first[i] = (r == 0 ? A[i] : r);

• Since \(F(p)\) is monotonically non-decreasing, binary search can be applied.

• \(V_i \times T\) can become very large, so the code uses __int128 to compute it safely.

  long long r = (long long)(((__int128)V[i] * T + R[i]) % A[i]);

• Prefix sums and stamina values can reach around \(10^{14}\), so long long is used.

  Source Code

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

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

    int N, L, Q;
    cin >> N >> L >> Q;

    vector<long long> A(N), R(N), V(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> R[i] >> V[i];
    }

    vector<long long> first(N);

    auto prefix_sum = [&](int pos) -> long long {
        long long res = 0;
        long long p = pos;
        for (int i = 0; i < N; i++) {
            if (first[i] <= p) {
                res += (p - first[i]) / A[i] + 1;
            }
        }
        return res;
    };

    while (Q--) {
        long long T, P;
        int S;
        cin >> T >> S >> P;

        for (int i = 0; i < N; i++) {
            long long r = (long long)(((__int128)V[i] * T + R[i]) % A[i]);
            first[i] = (r == 0 ? A[i] : r);
        }

        long long center = prefix_sum(S);
        long long low = center - P;
        long long high = center + P;

        int l = 0, r = L - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (prefix_sum(m) >= low) r = m;
            else l = m + 1;
        }
        int left = l;

        l = 0;
        r = L - 1;
        while (l < r) {
            int m = (l + r + 1) / 2;
            if (prefix_sum(m) <= high) l = m;
            else r = m - 1;
        }
        int right = l;

        cout << right - left + 1 << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.