Overview

In a business plan that repeats with a period of \(N\) days, given a specified starting day \(L\) and initial funds \(S\), the problem is to determine when the funds first become negative (i.e., when bankruptcy occurs). Since funds may continuously decrease and bankruptcy could occur after a very long period, we need to solve this efficiently using mathematical calculations and data structures rather than simulation.

Analysis

1. Expressing fund changes as formulas

Let \(D_i = A_i - B_i - C_i\) be the change in funds on day \(i\). The funds at the end of the \(k\)-th day from the start of business can be expressed as: $\(\text{Funds} = S + \sum_{d=1}^{k} D_{\text{(plan day corresponding to the } d\text{-th day from start)}}\)$

To compute this sum efficiently, we use prefix sums. To handle the periodicity, we prepare a prefix sum array \(P_i\) for \(2\) cycles of the plan (\(2N\) days), so that the change over \(N\) days starting from any starting day \(L\) can be expressed in a form like \(P_{L+r-1} - P_{L-2}\).

2. Determining whether bankruptcy occurs

Let \(T = \sum_{i=1}^N D_i\) be the total balance over one cycle (\(N\) days).

• If \(T \geq 0\): If the company survives the first \(N\) days (first cycle), then funds will not decrease (or will increase) afterwards, so bankruptcy will never occur.
• If \(T < 0\): Since funds decrease by \(|T|\) with each cycle, bankruptcy will inevitably occur at some point.

3. Identifying the timing of bankruptcy

We separate the problem into determining “which cycle” and “which day within that cycle” bankruptcy occurs.

1. If bankruptcy occurs within the first \(N\) days: Let \(M\) be the minimum relative fund change within the first cycle. If \(S + M < 0\), then bankruptcy occurs during this cycle.
2. If bankruptcy occurs in a later cycle: If \(T < 0\) and the company survives the first cycle, bankruptcy will occur after some number of cycles. The fund trajectory after \(q\) cycles is the first cycle’s trajectory shifted down by \(q \times T\). The value of \(q\) such that “the company survives up to cycle \(q\) but goes bankrupt in cycle \(q+1\)” can be found by solving the inequality \(S + qT + M < 0\), giving \(q = \lfloor (S+M)/|T| \rfloor + 1\).

To identify the specific “day,” we need to find “the first index where the value becomes less than a certain threshold” in the prefix sum array. This can be done in \(O(\log N)\) per query using a segment tree.

Algorithm

1. Preprocessing:
   • Compute the daily balance \(D_i\) and create a prefix sum array \(P\) of length \(2N\) (for 2 cycles).
   • Build a segment tree based on \(P\) that supports “range minimum queries” and “finding the first position in a range where the value is less than \(V\).”
2. Query processing:
   • Use the segment tree to find the minimum relative change \(M\) over the \(N\) days starting from day \(L\).
   • If \(S + M \geq 0\) and \(T \geq 0\), bankruptcy never occurs, so output 0.
   • Otherwise, compute the cycle \(q\) in which bankruptcy occurs (if \(S + M < 0\), then \(q=0\)).
   • In the fund situation after \(q\) cycles, use the segment tree’s find_first (binary search) to identify the first day when funds become negative.

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Building the segment tree takes \(O(N)\).
  • Each query performs a minimum query and binary search in \(O(\log N)\), so the total is \(O(Q \log N)\).
• Space complexity: \(O(N)\)
  • The prefix sum array and segment tree use \(O(N)\) memory.

Implementation Notes

• Handling periodicity: By maintaining an array of size \(2N\), regardless of the starting day \(L\), we can treat the range from day \(L\) to day \(L+N-1\) as a contiguous interval, simplifying the implementation.

• Binary search on the segment tree: When searching for “the first element whose value is less than \(V\),” performing a naive binary search outside the segment tree would result in \(O(\log^2 N)\), but traversing the segment tree nodes directly achieves \(O(\log N)\).

• Overflow: Prefix sums and initial funds \(S\) can exceed \(10^{12}\), and intermediate calculations may produce even larger values, so long long (64-bit integers) must be used.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Segment Tree to find the minimum value in a range and the first index satisfying a condition.
 * This will help in determining the first day the funds drop below zero.
 */
struct SegmentTree {
    int n;
    vector<long long> tree;
    static constexpr long long INF = 2e18; // Larger than any possible prefix sum

    SegmentTree(const vector<long long>& data) {
        n = (int)data.size();
        tree.resize(4 * n);
        build(data, 1, 0, n - 1);
    }

    // Build the segment tree with minimum values in each range.
    void build(const vector<long long>& data, int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(data, 2 * node, start, mid);
        build(data, 2 * node + 1, mid + 1, end);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }

    // Range minimum query to find the lowest fund level in a cycle.
    long long query_min(int node, int start, int end, int L, int R) {
        if (R < start || end < L) return INF;
        if (L <= start && end <= R) return tree[node];
        int mid = start + (end - start) / 2;
        return min(query_min(2 * node, start, mid, L, R),
                   query_min(2 * node + 1, mid + 1, end, L, R));
    }

    /**
     * Find the first index in [L, R] such that data[index] < V.
     * This is used to find the specific day of bankruptcy.
     */
    int find_first(int node, int start, int end, int L, int R, long long V) {
        // If the range is invalid or the minimum in this range is not less than V, return -1.
        if (R < start || end < L || tree[node] >= V) return -1;
        if (start == end) return start;
        int mid = start + (end - start) / 2;
        int res = find_first(2 * node, start, mid, L, R, V);
        if (res == -1) {
            res = find_first(2 * node + 1, mid + 1, end, L, R, V);
        }
        return res;
    }
};

int main() {
    // Fast I/O for competitive programming performance.
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // Daily net change in funds: D_i = A_i - B_i - C_i
    vector<long long> D(N);
    for (int i = 0; i < N; ++i) {
        long long A, B, C;
        cin >> A >> B >> C;
        D[i] = A - B - C;
    }

    // Prefix sums for two cycles (2N days) to handle the wrap-around logic easily.
    // P_data[i] stores the sum of D from day 1 to day i+1.
    vector<long long> P_data(2 * N);
    long long current_P = 0;
    for (int i = 0; i < 2 * N; ++i) {
        current_P += D[i % N];
        P_data[i] = current_P;
    }

    // Total fund change over one full cycle of N days.
    long long T = P_data[N - 1];

    // Build the segment tree on the prefix sums of the extended sequence.
    SegmentTree st(P_data);

    for (int j = 0; j < Q; ++j) {
        int L;
        long long S;
        cin >> L >> S;

        // P_prev is the prefix sum before starting on day L.
        long long P_prev = (L == 1) ? 0 : P_data[L - 2];
        
        // M is the minimum relative change in funds within the first N days starting from L.
        // The funds after r days starting from L are S + P_{L+r-1} - P_{L-1}.
        long long M = st.query_min(1, 0, 2 * N - 1, L - 1, L + N - 2) - P_prev;

        if (S + M >= 0) {
            // If the company survives the first full cycle starting from day L.
            if (T >= 0) {
                // If the net cycle change is non-negative, it will never bankrupt.
                cout << 0 << "\n";
            } else {
                // If the net cycle change is negative, it will eventually bankrupt.
                long long absT = -T;
                // Calculate how many full cycles q it takes before it enters a cycle where it bankrupts.
                // Bankruptcy condition: S + q*T + M < 0  =>  q*|T| > S + M
                long long q = (S + M) / absT + 1;
                long long S_prime = S + q * T;
                long long V = P_prev - S_prime;
                
                // Find the first day within the (q+1)-th cycle where bankruptcy happens.
                int idx = st.find_first(1, 0, 2 * N - 1, L - 1, L + N - 2, V);
                long long r = (long long)idx - L + 2;
                cout << (long long)q * N + r << "\n";
            }
        } else {
            // Bankruptcy occurs within the first cycle of N days.
            long long V = P_prev - S;
            int idx = st.find_first(1, 0, 2 * N - 1, L - 1, L + N - 2, V);
            long long r = (long long)idx - L + 2;
            cout << r << "\n";
        }
    }

    return 0;
}

---

This editorial was generated by gemini-3-flash-thinking.