Overview

This problem asks us to determine the range of rooms that Takahashi can reach within his stamina limit at a specific time, given corridors that are periodically locked. By leveraging the fact that the cumulative sum of door weights (number of locks) is monotonically increasing, we use binary search to identify the reachable left and right boundaries.

Analysis

1. Door Weights and Cumulative Sums

When we fix time \(T_j\), the weight (number of locks) of each door \(x\) is determined. The total weight of doors passed through when moving from room \(S_j\) to room \(c\) is the sum of weights over the interval of door numbers.

Here, we define \(D(x)\) as the total weight from door \(1\) to door \(x\). - When moving from room \(S_j\) to a room \(c\) on the right (\(c > S_j\)), the doors passed through are \(S_j+1, \dots, c\), so the total weight is \(D(c) - D(S_j)\). - When moving from room \(S_j\) to a room \(c\) on the left (\(c < S_j\)), the doors passed through are \(c+1, \dots, S_j\), so the total weight is \(D(S_j) - D(c)\).

2. Efficient Computation of \(D(x)\)

The condition for security pattern \(i\) to place a lock on door \(x\) is \(x \equiv (R_i + V_i \cdot T_j) \pmod{A_i}\). Let \(R'_i = (R_i + V_i \cdot T_j) \pmod{A_i}\). Then the door numbers locked by pattern \(i\) are \(R'_i, R'_i + A_i, R'_i + 2A_i, \dots\) (However, since door numbers start from \(1\), if \(R'_i = 0\), they become \(A_i, 2A_i, \dots\))

In this case, the number of locks from pattern \(i\) in the interval \([1, x]\), where \(f_i\) is the position of the first lock, is: - When \(x < f_i\): \(0\) - When \(x \geq f_i\): \(\lfloor (x - f_i) / A_i \rfloor + 1\)

By summing this over all \(N\) patterns, we can compute \(D(x)\) in \(O(N)\).

3. Determining the Range via Binary Search

Since the total weight of doors passed through increases as the travel distance increases (monotonically increasing), binary search can be applied. - How far right can we go: Find the maximum \(mid \in [S_j, L-1]\) satisfying \(D(mid) - D(S_j) \leq P_j\). - How far left can we go: Find the minimum \(mid \in [0, S_j]\) satisfying \(D(S_j) - D(mid) \leq P_j\).

Algorithm

1. For each query \((T_j, S_j, P_j)\), do the following.
2. Preprocessing: For each security pattern \(i\), compute the smallest lock position \(f_i\) at time \(T_j\).
3. Binary search to the right:
   • Set low = Sj, high = L - 1, and find the maximum mid satisfying D(mid) - D(Sj) <= Pj as ansR.
4. Binary search to the left:
   • Set low = 0, high = Sj, and find the minimum mid satisfying D(Sj) - D(mid) <= Pj as ansL.
5. Answer: The number of reachable rooms is ansR - ansL + 1.

Complexity

• Time Complexity: \(O(NQ \log L)\)
  • For each query, we perform \(O(N)\) preprocessing and \(O(N \log L)\) binary search (since computing \(D(x)\) takes \(O(N)\)).
  • Due to the constraint \(N \times Q \le 3 \times 10^5\), this complexity fits within the time limit.
• Space Complexity: \(O(N)\)
  • Memory is needed to store the security pattern information.

Implementation Notes

• Handling \(R'_i = 0\): Since door numbers start from \(1\), when the remainder is \(0\), the first door is \(A_i\), not \(0\).

• Overflow: The stamina \(P_j\) and total weight \(D(x)\) can become very large values (up to around \(10^{14}\)), so long long types must be used.

• Optimization: Since \(N \times Q\) can be large, in C++ it is recommended to use cin.tie(nullptr); ios::sync_with_stdio(false); to speed up input/output.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

/**
 * get_D calculates the prefix sum of door weights from door 1 up to door x.
 * A door x (1 <= x <= L-1) has a lock from security pattern i if
 * x ≡ (R_i + V_i * T_j) (mod A_i).
 * 
 * Let R'_i = (R_i + V_i * T_j) mod A_i.
 * The smallest k >= 1 such that k ≡ R'_i (mod A_i) is:
 * - A_i if R'_i == 0
 * - R'_i if R'_i > 0
 * Let this smallest k be first_k[i].
 * The number of such k in [1, x] is:
 * - 0 if x < first_k[i]
 * - floor((x - first_k[i]) / A_i) + 1 if x >= first_k[i]
 */
long long get_D(long long x, int N, const vector<long long>& first_k, const vector<long long>& A) {
    if (x <= 0) return 0;
    long long total = 0;
    for (int i = 0; i < N; ++i) {
        if (x >= first_k[i]) {
            total += (x - first_k[i]) / A[i] + 1;
        }
    }
    return total;
}

struct Pattern {
    long long A, R, V;
};

int main() {
    // Faster I/O for competitive programming
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long L;
    int Q;
    if (!(cin >> N >> L >> Q)) return 0;

    // Store security patterns
    vector<Pattern> patterns(N);
    for (int i = 0; i < N; ++i) {
        cin >> patterns[i].A >> patterns[i].R >> patterns[i].V;
    }

    // Vectors to store precomputed values for each query
    vector<long long> first_k(N);
    vector<long long> A_vals(N);

    // Process each query
    for (int j = 0; j < Q; ++j) {
        long long Tj, Sj, Pj;
        cin >> Tj >> Sj >> Pj;

        // Precompute the smallest door index for each pattern at time Tj
        for (int i = 0; i < N; ++i) {
            long long Ri_prime = (patterns[i].R + patterns[i].V * Tj) % patterns[i].A;
            first_k[i] = (Ri_prime == 0 ? patterns[i].A : Ri_prime);
            A_vals[i] = patterns[i].A;
        }

        // Prefix sum of door weights up to room Sj
        long long D_Sj = get_D(Sj, N, first_k, A_vals);

        // Binary search for the rightmost reachable room ansR in [Sj, L-1]
        // Sum of weights of doors between Sj and mid (mid > Sj) is D(mid) - D(Sj)
        long long lowR = Sj, highR = L - 1;
        long long ansR = Sj;
        while (lowR <= highR) {
            long long mid = lowR + (highR - lowR) / 2;
            if (get_D(mid, N, first_k, A_vals) - D_Sj <= Pj) {
                ansR = mid;
                lowR = mid + 1;
            } else {
                highR = mid - 1;
            }
        }

        // Binary search for the leftmost reachable room ansL in [0, Sj]
        // Sum of weights of doors between mid and Sj (mid < Sj) is D(Sj) - D(mid)
        long long lowL = 0, highL = Sj;
        long long ansL = Sj;
        while (lowL <= highL) {
            long long mid = lowL + (highL - lowL) / 2;
            if (D_Sj - get_D(mid, N, first_k, A_vals) <= Pj) {
                ansL = mid;
                highL = mid - 1;
            } else {
                lowL = mid + 1;
            }
        }

        // Output the number of reachable rooms in the range [ansL, ansR]
        cout << ansR - ansL + 1 << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3-flash-thinking.