Overview

Define the daily fund change as \(d_i=A_i-B_i-C_i\), and for each query, find “the first day when cumulative funds become negative” on a periodically repeating sequence.

Prepare prefix sums for \(2N\) days, and use a segment tree to efficiently find the range minimum and “the first position where the value falls below a certain threshold.”

Analysis

First, define the daily fund change as

\[ d_i = A_i - B_i - C_i \]

Since the business plan repeats with period \(N\), we can think of \(d_1,d_2,\ldots,d_N\) as a sequence that repeats infinitely.

When a query starts from day \(L\), the first \(N\) days follow the order

\[ L,L+1,\ldots,N,1,2,\ldots,L-1 \]

To handle such “intervals that start midway and wrap around,” we consider prefix sums of the sequence repeated \(2\) times.

Define the prefix sums as

\[ p_0=0 \]

\[ p_i=p_{i-1}+d_{((i-1)\bmod N)+1} \]

Then, when starting from day \(L\), the cumulative fund change after \(t\) days \((1 \leq t \leq N)\) from the start is

\[ p_{L+t-1} - p_{L-1} \]

Since the initial funds are \(S\) yen, the bankruptcy condition is

\[ S + p_{L+t-1} - p_{L-1} < 0 \]

Rearranging this gives

\[ p_{L+t-1} < p_{L-1} - S \]

In other words, we need to find the first position within the interval \([L, L+N-1]\) where the prefix sum falls below a certain value.

However, since the prefix sums are not necessarily monotonic, simple binary search cannot be used.
Also, checking \(N\) days for each query would result in \(O(NQ)\), which may not be fast enough.

Therefore, we use a segment tree to efficiently perform the following operations:

• Find the minimum value in a range
• Find the first position in a range where the value falls below \(x\)

Next, define the total change over \(1\) cycle as

\[ T = d_1+d_2+\cdots+d_N \]

Case \(T \geq 0\)

Since funds do not decrease after completing each cycle, each subsequent cycle starts with the same or more funds than the previous one.

Therefore, if bankruptcy does not occur in the first cycle, it will never occur afterward.

So, in the interval \([L,L+N-1]\), we search for the first position \(k\) where

\[ p_k < p_{L-1}-S \]

If found, the answer is

\[ k-L+1 \]

days.

If not found, the answer is \(0\).

Case \(T < 0\)

Since funds decrease with each cycle, bankruptcy will eventually occur.

However, if the initial funds \(S\) are large, the business may survive for many cycles.
Simulating day by day would be too slow.

First, find the minimum fund change within one cycle starting from day \(L\).

Let the minimum prefix sum in the interval \([L,L+N-1]\) be \(\min p_k\). Then the worst fund change within one cycle is

\[ m = \min_{k \in [L,L+N-1]} p_k - p_{L-1} \]

After \(c\) cycles have elapsed, the funds at the start of the next cycle are

\[ S + cT \]

The minimum funds during that cycle are

\[ S + cT + m \]

We find the smallest \(c\) such that this becomes negative for the first time.

Since \(T<0\), let \(D=-T\), so funds decrease by \(D\) per cycle.

If

\[ S+m<0 \]

then bankruptcy occurs in the first cycle, so \(c=0\).

Otherwise,

\[ c = \left\lfloor \frac{S+m}{D} \right\rfloor + 1 \]

This \(c\) represents “how many cycles have been completed before the cycle in which bankruptcy occurs.”

Within that cycle, the bankruptcy condition is

\[ S+cT+p_k-p_{L-1}<0 \]

Rearranging gives

\[ p_k < p_{L-1}-S-cT \]

Again using the segment tree, we search for the first position \(k\) in the interval \([L,L+N-1]\) that satisfies this condition.

The answer is

\[ cN + (k-L+1) \]

Algorithm

1. Compute the daily change \(d_i=A_i-B_i-C_i\) for each day.
2. Create prefix sums \(p\) for \(2N\) days to handle intervals that span the period boundary.
3. Build a segment tree on the prefix sums \(p\).
4. Process each query \((L,S)\):
   • \(base=p_{L-1}\)
   • \(R=L+N-1\)
   • \(T=p_N\)
5. Case \(T \geq 0\):
   • Search for the first \(k \in [L,R]\) where \(p_k < base-S\).
   • If found, output \(k-L+1\); otherwise, output \(0\).
6. Case \(T < 0\):
   • Find the minimum value in the interval \([L,R]\), and let \(m=\min p_k-base\).
   • Determine the cycle number \(c\) in which bankruptcy occurs.
   • Search for the first \(k \in [L,R]\) where \(p_k < base-S-cT\).
   • Output \(cN+(k-L+1)\).

Complexity

• Time complexity: \(O((N+Q)\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

The bankruptcy condition is “funds become less than \(0\) yen,” so the comparison is

\[ < 0 \]

Therefore, when searching the prefix sums, the condition is also a strict inequality:

\[ p_k < \text{limit} \]

Be careful not to use \(\leq\), as that would incorrectly treat the case where funds are exactly \(0\) yen as bankruptcy.

Also, since prefix sums and answers can become large, use long long.

Source Code

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

using ll = long long;
const ll INF = (1LL << 62);

struct SegTree {
    int n, m;
    vector<ll> seg;

    SegTree(const vector<ll>& a) {
        m = (int)a.size();
        n = 1;
        while (n < m) n <<= 1;
        seg.assign(2 * n, INF);
        for (int i = 0; i < m; i++) seg[n + i] = a[i];
        for (int i = n - 1; i >= 1; i--) {
            seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
        }
    }

    ll range_min(int l, int r) const {
        ll res = INF;
        l += n;
        r += n;
        while (l <= r) {
            if (l & 1) res = min(res, seg[l++]);
            if (!(r & 1)) res = min(res, seg[r--]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }

    int first_less_rec(int node, int nl, int nr, int ql, int qr, ll x) const {
        if (qr < nl || nr < ql || seg[node] >= x) return -1;
        if (nl == nr) return nl;
        int mid = (nl + nr) >> 1;
        int res = first_less_rec(node << 1, nl, mid, ql, qr, x);
        if (res != -1) return res;
        return first_less_rec(node << 1 | 1, mid + 1, nr, ql, qr, x);
    }

    int first_less(int l, int r, ll x) const {
        return first_less_rec(1, 0, n - 1, l, r, x);
    }
};

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

    int N, Q;
    cin >> N >> Q;

    vector<ll> d(N + 1);
    for (int i = 1; i <= N; i++) {
        ll A, B, C;
        cin >> A >> B >> C;
        d[i] = A - B - C;
    }

    vector<ll> pref(2 * N + 1, 0);
    for (int i = 1; i <= 2 * N; i++) {
        pref[i] = pref[i - 1] + d[(i - 1) % N + 1];
    }

    ll total = pref[N];
    SegTree seg(pref);

    while (Q--) {
        int L;
        ll S;
        cin >> L >> S;

        ll base = pref[L - 1];
        int R = L + N - 1;

        if (total >= 0) {
            ll limit = base - S;
            int idx = seg.first_less(L, R, limit);
            if (idx == -1) {
                cout << 0 << '\n';
            } else {
                cout << (ll)(idx - L + 1) << '\n';
            }
        } else {
            ll min_pref = seg.range_min(L, R);
            ll mn = min_pref - base;

            ll cycles = 0;
            ll val = S + mn;
            if (val >= 0) {
                ll dec = -total;
                cycles = val / dec + 1;
            }

            ll threshold = -S - cycles * total;
            ll limit = base + threshold;
            int idx = seg.first_less(L, R, limit);

            ll ans = cycles * (ll)N + (ll)(idx - L + 1);
            cout << ans << '\n';
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.