概要

各時刻で「どの扉に何個の錠があるか」を数え、部屋間移動コストを扉重さの累積和で表す問題です。
累積和関数 \(F(x)\) を作れると、到達可能範囲は左右それぞれ二分探索で求められます。

考察

まず、質問 \((T,S,P)\) を固定して考えます。
時刻 \(T\) において、パターン \(i\) が錠をかける扉は

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

です。
扉 \(x\) の重さは「この合同式を満たすパターン数」です。

---

部屋 \(S\) から部屋 \(c\) への移動コストは、間にある扉重さの総和です。
ここで

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

（\(w(d)\) は扉 \(d\) の重さ）とすると、

• \(c\ge S\) のときコスト \(=F(c)-F(S)\)
• \(c\le S\) のときコスト \(=F(S)-F(c)\)

となります。
つまり「到達可能な \(c\)」は、\(F\) が単調非減少であることから連続区間になります。

---

素朴解が厳しい理由

• 各扉の重さを全扉（最大 \(10^9\) 本近い）について作るのは不可能。
• 各質問ごとに全扉を走査するのも不可能。

---

重要な工夫

\(F(x)\) を直接 \(O(N)\) で計算します。
各パターン \(i\) について、\(1..x\) の中で

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

を満たす個数を数えればよいです。

• \(B_i=0\) のとき: 該当扉は \(A_i,2A_i,\dots\)
  個数は \(\left\lfloor \dfrac{x}{A_i}\right\rfloor\)
• \(B_i>0\) のとき: 最初は \(B_i\)、以降 \(A_i\) 間隔
  \(x\ge B_i\) なら \(1+\left\lfloor \dfrac{x-B_i}{A_i}\right\rfloor\)、そうでなければ \(0\)

これを全パターンで足せば \(F(x)\)。

さらに、到達可能範囲は以下で求まります。

• 右端: 最大の \(c\in[S,L-1]\) で \(F(c)\le F(S)+P\)
• 左端: 最小の \(c\in[0,S]\) で \(F(c)\ge F(S)-P\)

どちらも二分探索可能です（\(F\) が単調なので）。

アルゴリズム

各質問ごとに:

1. 各パターンの \(B_i=(R_i+V_iT)\bmod A_i\) を計算
2. 関数 pref(x)=F(x) を \(O(N)\) で計算できるようにする
3. \(FS=F(S)\) を計算
4. 二分探索で右端 rightMost を求める
   条件: pref(mid) <= FS + P
5. 二分探索で左端 leftMost を求める
   条件: pref(mid) >= FS - P
6. 答えは rightMost - leftMost + 1

この方法は、コード中コメントの通り \(N\times Q\le 3\times 10^5\) を活かして、
「1質問あたり \(O(N\log L)\)」で十分間に合います。

計算量

• 時間計算量: \(O(Q \cdot N \cdot \log L)\)
• 空間計算量: \(O(N)\)（1質問中に使う配列）

実装のポイント

• \(R_i+V_iT\) は最大で大きくなるため、__int128 で計算してから mod を取る。

• pref(x) は \(x=0\) のとき \(0\) を返すようにする（境界の安全性）。

• 左右で二分探索の条件が異なる点に注意。

  • 右は「条件を満たす最大値」
  • 左は「条件を満たす最小値」

• 累積和の合計も大きくなりうるため、内部和を __int128 にしておくと安全です。

  ソースコード

#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;
}

---

この解説は gpt-5.3-codex によって生成されました。