Overview

In a business plan that repeats an \(N\)-day cycle infinitely, for each query we need to efficiently determine “starting from day \(L\) with initial funds \(S\), on which day does bankruptcy first occur?”

Analysis

Key Insight

Define the daily fund change as \(D_i = A_i - B_i - C_i\), and the prefix sum \(P[i] = \sum_{k=1}^{i} D_k\) (with \(P[0] = 0\)).

When starting business from day \(L\) with initial funds \(S\), the funds at the end of the \(k\)-th day counting from day \(L\) (plan day \(d\)) are: $\(S + P[d] - P[L-1]\)$ (within the same cycle)

The bankruptcy condition is \(S + P[d] - P[L-1] < 0\), that is: $\(P[d] < P[L-1] - S\)$

Handling Cycles

After the first incomplete cycle (day \(L\) through day \(N\)), during day \(k\) of the \((m+1)\)-th complete cycle (after \(m\) complete cycles), the funds are: $\(S + (P[N] - P[L-1]) + m \cdot T + P[k] = S - P[L-1] + (m+1) \cdot T + P[k]\)$

Here \(T = P[N]\) (net profit per cycle). The bankruptcy condition is: $\(P[k] < P[L-1] - S - (m+1) \cdot T\)$

Case Analysis

• When \(T \geq 0\): As cycles accumulate, the threshold decreases, so we only need to check the first incomplete cycle and the first complete cycle. If bankruptcy doesn’t occur in either, it never will.
• When \(T < 0\): As cycles accumulate, the threshold increases, and bankruptcy will inevitably occur. We calculate which cycle bankruptcy first occurs in.

Algorithm

1. Preprocessing: Compute the prefix sum \(P[i]\) and store it in a segment tree. The segment tree manages range minimums and can find “the leftmost position with a value less than a given threshold” in \(O(\log N)\).

2. Processing each query:

   • First incomplete cycle (\([L, N]\)): Search for the leftmost \(k\) where \(P[k] < P[L-1] - S\). If found, the answer is \(k - L + 1\).
   • When \(T \geq 0\): Search \([1, N]\) with threshold \(P[L-1] - S - T\). If found, the answer is \((N - L + 1) + k\); if not found, the answer is \(0\) (no bankruptcy).
   • When \(T < 0\): Using the overall minimum \(\min P\), compute the first cycle number \(m\) where bankruptcy occurs in \(O(1)\): $\(m = \left\lfloor \frac{-(P[L-1] - S - \min P)}{-T} \right\rfloor\)\( Within that cycle, find the leftmost position \)k\( using threshold \)P[L-1] - S - (m+1) \cdot T\(, and the answer is \)(N - L + 1) + m \cdot N + k$.

Complexity

• Time complexity: \(O(N + Q \log N)\)
  • \(O(N)\) for segment tree construction, \(O(\log N)\) per query for segment tree searches
• Space complexity: \(O(N)\)
  • Segment tree and prefix sum array

Implementation Notes

• Use long long since funds and prefix sums can become very large (\(S\) can be up to \(10^{12}\), and prefix sums can also grow large).

• Design the segment tree to return \(-1\) when no position satisfying “leftmost position below threshold” exists.

• When \(T < 0\), perform integer division correctly when computing \(m\) (if \(R = P[L-1] - S - \min P\) is non-negative, then \(m = 0\)).

• Align the segment tree size to a power of 2, and initialize unused parts with LLONG_MAX (a sufficiently large value) to prevent out-of-range effects.

  Source Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<long long> P(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        P[i] = P[i-1] + (a - b - c);
    }
    
    long long T = P[N];
    
    int sz = 1;
    while (sz < N) sz *= 2;
    vector<long long> tree(2 * sz, LLONG_MAX);
    for (int i = 1; i <= N; i++) {
        tree[sz + i - 1] = P[i];
    }
    for (int i = sz - 1; i >= 1; i--) {
        tree[i] = min(tree[2*i], tree[2*i+1]);
    }
    
    long long minP = tree[1];
    
    function<int(int, int, int, int, int, long long)> find_left = 
        [&](int node, int nl, int nr, int ql, int qr, long long thresh) -> int {
        if (nl > qr || nr < ql) return -1;
        if (tree[node] >= thresh) return -1;
        if (nl == nr) return nl;
        int mid = (nl + nr) / 2;
        int res = find_left(2*node, nl, mid, ql, qr, thresh);
        if (res != -1) return res;
        return find_left(2*node+1, mid+1, nr, ql, qr, thresh);
    };
    
    auto query = [&](int l, int r, long long threshold) -> int {
        return find_left(1, 1, sz, l, r, threshold);
    };
    
    for (int q = 0; q < Q; q++) {
        int L;
        long long S;
        cin >> L >> S;
        
        long long thresh1 = P[L-1] - S;
        int pos = query(L, N, thresh1);
        if (pos != -1) {
            cout << (pos - L + 1) << "\n";
            continue;
        }
        
        if (T >= 0) {
            long long thresh = P[L-1] - S - T;
            int pos2 = query(1, N, thresh);
            if (pos2 != -1) {
                cout << (long long)(N - L + 1) + pos2 << "\n";
            } else {
                cout << 0 << "\n";
            }
        } else {
            long long R = P[L-1] - S - minP;
            long long m;
            if (R >= 0) {
                m = 0;
            } else {
                m = (-R) / (-T);
            }
            long long thresh = P[L-1] - S - (m + 1) * T;
            int pos2 = query(1, N, thresh);
            long long answer = (long long)(N - L + 1) + (long long)m * N + pos2;
            cout << answer << "\n";
        }
    }
    
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.