まず、\(f _ t(n)\coloneqq\) 時刻 \(t\) において部屋 \(0\) から部屋 \(n\) までの間にかけられている錠の数 \((0\le n\lt L)\) として定めます。 これは \(O(N)\) 時間で計算することができます。

すると、ひとつの質問 \((T _ j,S _ j,P _ j)\) に対する答えは次のように求めることができます。

\(l\) を \(f _ {T _ j}(S _ j)-P _ j\le f _ {T _ j}(l)\) を満たす最小の整数、\(r\) を \(f _ {T _ j}( r)\le f _ {T _ j}(S _ j)+P _ j\) を満たす最大の整数とする。求める答えは \(r-l+1\) である。

よって、\(l,r\) を高速に求められればこの問題を解くことができます。 これは、二分探索を用いることで \(O(\log L)\) 回 \(f _ {T _ j}\) を計算して \(l,r\) を求めることができます。

時間計算量は \(O(NQ\log L)\) となり、十分高速です。

実装例は以下のようになります。 二分探索の判定では \(f _ {T _ j}\) の具体的な値ではなく同じ \(T _ j\) に対する差のみが使われることから、以下の実装例では \(f _ t\) の計算式を少し単純にしています。

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int main() {
    int N, L, Q;
    cin >> N >> L >> Q;

    vector<tuple<int, int, int>> security(N);
    for (auto&& [A, R, V] : security) {
        cin >> A >> R >> V;
    }

    // 時刻 t に部屋 x 以下に存在する鍵の本数
    auto count = [&security](long t, long x) -> long {
        long ans = 0;
        for (const auto [A, R, V] : security) {
            ans += (x + A - (R + V * t) % A) / A;
        }
        return ans;
    };

    for (int i = 0; i < Q; ++i) {
        int T, S;
        long P;
        cin >> T >> S >> P;
        long base = count(T, S); // f(S) を求める

        // f(S)-P <= f(left) となる最小の整数
        long left = S;
        {
            long left_lower_bound = -1;
            while (left_lower_bound + 1 < left) {
                long mid = (left_lower_bound + left) / 2;
                if (count(T, mid) + P < base) {
                    left_lower_bound = mid;
                } else {
                    left = mid;
                }
            }
        }

        // f(S)+P < f(right) となる最小の整数
        long right = L;
        {
            long right_lower_bound = S;
            while (right_lower_bound + 1 < right) {
                long mid = (right_lower_bound + right) / 2;
                if (base + P < count(T, mid)) {
                    right = mid;
                } else {
                    right_lower_bound = mid;
                }
            }
        }
        cout << right - left << endl;
    }
    return 0;
}

N, L, Q = map(int, input().split())

security = [tuple(map(int, input().split())) for _ in range(N)]

# 時刻 t に部屋 x 以下に存在する鍵の本数
def count(t, x):
    ans = 0
    for A, R, V in security:
        ans += (x + A - (R + V * t) % A) // A
    return ans

for _ in range(Q):
    T, S, P = map(int, input().split())

    base = count(T, S) # f(S) を求める

    # f(S) - P <= f(left) となる最小の整数
    left = S
    left_lower_bound = -1
    while left_lower_bound + 1 < left:
        mid = (left_lower_bound + left) // 2
        if count(T, mid) + P < base:
            left_lower_bound = mid
        else:
            left = mid

    # f(S) + P < f(right) となる最小の整数
    right = L
    right_lower_bound = S
    while right_lower_bound + 1 < right:
        mid = (right_lower_bound + right) // 2
        if base + P < count(T, mid):
            right = mid
        else:
            right_lower_bound = mid

    print(right - left)