概要

時刻ごとに各扉の重さを直接列挙するのではなく、「扉 \(1\) から扉 \(y\) までにある錠の総数」を高速に計算できるようにします。
その累積和を使うと、ある部屋まで移動するのに必要な体力を求められるため、到達可能な左右端を二分探索で求めます。

考察

扉は \(1\) から \(L-1\) までありますが、\(L\) は最大 \(10^9\) なので、各扉の重さを配列で持つことはできません。

そこで、ある時刻 \(T\) において、警備パターン \(i\) が錠をかける扉を考えます。

警備パターン \(i\) は、扉 \(x\) が

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

を満たすとき錠をかけます。

ここで

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

とします。

扉番号は \(1\) 以上なので、最初に現れる扉番号 \(f_i\) は次のようになります。

• \(b_i > 0\) のとき、\(f_i = b_i\)
• \(b_i = 0\) のとき、\(f_i = A_i\)

例えば \(A_i=5, b_i=2\) なら、錠がかかる扉は

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

です。

一方、\(A_i=5, b_i=0\) なら、錠がかかる扉は

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

です。

つまり、各警備パターンが錠をかける扉は等差数列になります。

---

ここで、時刻 \(T\) における

\[ C(y) = \text{扉 }1\text{ から扉 }y\text{ までの重さの総和} \]

を考えます。

警備パターン \(i\) が扉 \(1\) から扉 \(y\) までに錠をかける個数は、

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

です。

したがって、\(C(y)\) は全警備パターンについてこの値を足し合わせれば求められます。

---

部屋 \(S\) から部屋 \(c\) へ移動するコストを考えます。

右へ移動する場合

\(S \leq c\) のとき、通る扉は

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

です。

したがって必要な体力は

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

です。

左へ移動する場合

\(c \leq S\) のとき、通る扉は

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

です。

したがって必要な体力は

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

です。

---

\(C(y)\) は \(y\) が大きくなるほど増える、つまり単調非減少です。
そのため、到達可能な右端・左端は二分探索で求められます。

素朴に各部屋を調べると \(O(L)\) かかり、\(L \leq 10^9\) なので間に合いません。
また、各扉を列挙することも不可能です。

しかし、累積和 \(C(y)\) を \(O(N)\) で計算できれば、二分探索により各質問を \(O(N \log L)\) で処理できます。
制約に \(N \times Q \leq 3 \times 10^5\) があるため、これは十分間に合います。

アルゴリズム

各質問 \((T, S, P)\) について以下を行います。

まず、時刻 \(T\) における各警備パターンの最初の扉番号 \(f_i\) を求めます。

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

として、

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

とします。

次に、関数 \(C(y)\) を次のように計算します。

\[ 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} \]

これは「扉 \(1\) から扉 \(y\) までにかかっている錠の総数」です。

---

まず

\[ C(S) \]

を計算します。

右端を求める

右側の部屋 \(c\) に到達できる条件は

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

です。

これは

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

と変形できます。

\(C(c)\) は単調非減少なので、条件を満たす最大の \(c\) を二分探索で求めます。

もし最も右の部屋 \(L-1\) までのコストが \(P\) 以下なら、右端はそのまま \(L-1\) です。

左端を求める

左側の部屋 \(c\) に到達できる条件は

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

です。

これは

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

と変形できます。

よって、条件を満たす最小の \(c\) を二分探索で求めます。

もし

\[ C(S) \leq P \]

なら、部屋 \(0\) まで到達できるので、左端は \(0\) です。

---

最終的に、到達可能な部屋は連続した区間になります。

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

したがって答えは

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

です。

計算量

• 時間計算量: \(O(NQ \log L)\)
• 空間計算量: \(O(N + Q)\)

各質問で累積和 \(C(y)\) の計算に \(O(N)\)、二分探索に \(O(\log L)\) 回の累積和計算を行います。
ただし制約で \(N \times Q \leq 3 \times 10^5\) なので、十分高速です。

実装のポイント

• 扉番号は \(1\) から始まりますが、部屋番号は \(0\) から始まる点に注意します。
• \(b_i = 0\) のとき、最初に錠がかかる扉は \(0\) ではなく \(A_i\) です。
  • そのため、コードでは ((R[i] + V[i] * T) % A[i]) or A[i] としています。
• prefix_sum(y) は扉 \(1\) から扉 \(y\) までの総和です。
  • 特に prefix_sum(0) は \(0\) になります。
• 各扉の重さは最大でも \(N\) なので、もし

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

なら、どちらの端まで行く場合でも必ず体力が足りるため、答えはすぐに \(L\) とできます。

ソースコード

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()

---

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