Overview

This problem requires counting “how many locks are on each door” at each time step, and expressing the movement cost between rooms as a prefix sum of door weights.
Once we can construct the prefix sum function \(F(x)\), the reachable range can be determined by binary search in both the left and right directions.

Analysis

First, let’s fix a query \((T,S,P)\) and think about it.
At time \(T\), the doors that pattern \(i\) locks are:

\[x \equiv B_i \pmod{A_i},\quad B_i=(R_i+V_iT)\bmod A_i\]

The weight of door \(x\) is “the number of patterns satisfying this congruence.”

---

The movement cost from room \(S\) to room \(c\) is the total sum of door weights between them.
If we define:

\[F(x)=\sum_{d=1}^{x} w(d)\]

(where \(w(d)\) is the weight of door \(d\)), then:

• When \(c\ge S\): cost \(=F(c)-F(S)\)
• When \(c\le S\): cost \(=F(S)-F(c)\)

In other words, the “reachable \(c\)” forms a contiguous interval, since \(F\) is monotonically non-decreasing.

---

Why a naive solution is infeasible

• It is impossible to compute the weight of every door (up to nearly \(10^9\) doors).
• It is also impossible to scan all doors for each query.

---

Key Insight

We compute \(F(x)\) directly in \(O(N)\).
For each pattern \(i\), we count how many values in \(1..x\) satisfy:

\[d \equiv B_i \pmod{A_i}\]

• When \(B_i=0\): the matching doors are \(A_i,2A_i,\dots\)
  The count is \(\left\lfloor \dfrac{x}{A_i}\right\rfloor\)
• When \(B_i>0\): the first is \(B_i\), then at intervals of \(A_i\)
  If \(x\ge B_i\), the count is \(1+\left\lfloor \dfrac{x-B_i}{A_i}\right\rfloor\); otherwise \(0\)

Summing this over all patterns gives \(F(x)\).

Furthermore, the reachable range can be determined as follows:

• Right endpoint: the maximum \(c\in[S,L-1]\) such that \(F(c)\le F(S)+P\)
• Left endpoint: the minimum \(c\in[0,S]\) such that \(F(c)\ge F(S)-P\)

Both can be found by binary search (since \(F\) is monotonic).

Algorithm

For each query:

1. Compute \(B_i=(R_i+V_iT)\bmod A_i\) for each pattern
2. Set up the function pref(x)=F(x) computable in \(O(N)\)
3. Compute \(FS=F(S)\)
4. Find the right endpoint rightMost by binary search
   Condition: pref(mid) <= FS + P
5. Find the left endpoint leftMost by binary search
   Condition: pref(mid) >= FS - P
6. The answer is rightMost - leftMost + 1

This method takes advantage of \(N\times Q\le 3\times 10^5\) as noted in the code comments,
and runs in \(O(N\log L)\) per query, which is sufficiently fast.

Complexity

• Time complexity: \(O(Q \cdot N \cdot \log L)\)
• Space complexity: \(O(N)\) (arrays used within a single query)

Implementation Notes

• \(R_i+V_iT\) can become very large, so compute it using __int128 before taking the modulus.

• pref(x) should return \(0\) when \(x=0\) (for boundary safety).

• Note that the binary search conditions differ for the left and right directions.

  • Right: “maximum value satisfying the condition”
  • Left: “minimum value satisfying the condition”

• Since the total of prefix sums can also become very large, it is safe to use __int128 for internal sums.

  Source Code

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

using int64 = long long;
using i128 = __int128_t;

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

struct Query {
    int64 T, S, P;
};

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

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

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

    vector<Query> qs(Q);
    for (int i = 0; i < Q; i++) {
        cin >> qs[i].T >> qs[i].S >> qs[i].P;
    }

    // Since N*Q <= 3e5, we can process each query with all patterns.
    // For each query, door weights are:
    // w(x) = number of i such that x ≡ Bi (mod Ai), where Bi = (Ri + Vi*T) mod Ai.
    // Need count of rooms c where sum of w on doors between S and c <= P.
    // Define F(x)=sum_{d=1..x} w(d), x in [0..L-1], F(0)=0 over doors index.
    // For c>=S: cost = F(c)-F(S)
    // For c<=S: cost = F(S)-F(c)
    //
    // We need:
    // rightmost c>=S with F(c) <= F(S)+P
    // leftmost c<=S with F(c) >= F(S)-P  (since F nondecreasing)
    //
    // F(x)=sum_i cnt_i(x), cnt_i(x)=# {d in [1..x] : d ≡ Bi mod Ai}
    // Each cnt_i(x) can be computed O(1).
    //
    // Then binary search on c with O(N) predicate each -> O(N log L) per query.
    // With N*Q<=3e5, and logL~30, this is acceptable in C++ with tight code.

    auto floor_div = [](int64 a, int64 b)->int64{
        // b>0, a>=0 in our use
        return a / b;
    };

    for (int qi = 0; qi < Q; qi++) {
        const auto &qu = qs[qi];
        int64 T = qu.T, S = qu.S, P = qu.P;

        vector<int64> A(N), B(N);
        A.reserve(N); B.reserve(N);

        for (int i = 0; i < N; i++) {
            A[i] = pat[i].A;
            i128 val = (i128)pat[i].V * (i128)T + (i128)pat[i].R;
            int64 b = (int64)(val % pat[i].A);
            if (b < 0) b += pat[i].A;
            B[i] = b;
        }

        auto pref = [&](int64 x)->int64{
            // sum over doors 1..x, x can be 0..L-1
            if (x <= 0) return 0;
            i128 sum = 0;
            for (int i = 0; i < N; i++) {
                int64 a = A[i], b = B[i];
                int64 cnt = 0;
                if (b == 0) {
                    // doors: a,2a,...
                    cnt = floor_div(x, a);
                } else {
                    if (x >= b) cnt = 1 + floor_div(x - b, a);
                    else cnt = 0;
                }
                sum += cnt;
            }
            return (int64)sum;
        };

        int64 FS = pref(S);

        // right bound
        int64 low = S, high = L - 1;
        int64 targetR = FS + P;
        while (low < high) {
            int64 mid = low + (high - low + 1) / 2;
            if (pref(mid) <= targetR) low = mid;
            else high = mid - 1;
        }
        int64 rightMost = low;

        // left bound
        low = 0; high = S;
        int64 targetL = FS - P;
        while (low < high) {
            int64 mid = low + (high - low) / 2;
            if (pref(mid) >= targetL) high = mid;
            else low = mid + 1;
        }
        int64 leftMost = low;

        cout << (rightMost - leftMost + 1) << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.