Overview

This is a problem where you answer \(Q\) queries, each asking for the “number of times the limit was reached \(C\)” and the “final stress value \(G\)” when processing \(N\) tasks in order. You need to solve it efficiently by leveraging the property that the stress value resets when it reaches or exceeds a threshold \(K\), and the fact that \(K\) is relatively small (\(K \leq 300\)).

Analysis

Issues with Naive Simulation

If we simulate tasks one by one in the specified range \([L, R]\) for each query, each query takes \(O(N)\) in the worst case. The total becomes \(O(QN)\), which won’t fit within the time limit given the constraints (\(N, Q \leq 6 \times 10^4\)).

Key Observation: Small \(K\)

The stress value \(G\) always falls within the range \(0 \leq G < K\) after Step 3 is processed. Since \(K\) is at most 300, which is very small, we focus on the fact that “if we know the stress value \(G\) at a certain point, the subsequent behavior is uniquely determined, and there are only \(K\) possible states.”

Solution: Square Root Decomposition

We introduce square root decomposition, dividing the sequence of tasks into blocks of size \(B\). For each block, we precompute the following values: - If the stress value at the start of the block is \(g \in [0, K-1]\): - What is the stress value after processing all tasks in the block? - How many times was the limit reached within the block?

This allows us to skip the simulation for “fully contained blocks” within a query’s range and simply accumulate the precomputed results.

Algorithm

1. Precomputation

1. Divide the \(N\) tasks into blocks of size \(B\) (e.g., around 200).
2. For each block \(b\), simulate the tasks within the block for each initial stress value \(g = 0, 1, \ldots, K-1\).
3. Store the results (final \(g\) and limit-reached count \(c\)) in block_f[block_id][initial_g].

2. Answering Queries

For a query \([L, R]\), compute as follows: 1. Left partial block: From \(L\) to the right end of the block containing \(L\), simulate one by one naively. 2. Middle complete blocks: From the block after \(L\)’s block to the block before \(R\)’s block, update \(G\) and \(C\) all at once using the precomputed block_f. 3. Right partial block: From the left end of the block containing \(R\) to \(R\), simulate one by one naively. ※ If \(L\) and \(R\) are in the same block, simulate the entire range naively.

Complexity

Let \(B\) be the block size.

• Precomputation: \(O(\frac{N}{B} \cdot B \cdot K) = O(NK)\)
  • There are \(\frac{N}{B}\) blocks, and for each block we simulate \(K\) initial values over a block of size \(B\).
• Queries: \(O(Q \cdot (B + \frac{N}{B}))\)
  • The partial simulation takes at most \(2B\), and jumping through blocks takes at most \(\frac{N}{B}\).

The overall complexity is \(O(NK + Q(B + \frac{N}{B}))\). With \(N, Q = 6 \times 10^4, K = 300, B = 200\), the precomputation is approximately \(1.8 \times 10^7\) and query processing is approximately \(3 \times 10^7\), which fits well within the time limit.

Implementation Notes

• Stress value update formula: Steps 1 and 2 can be combined as \(G = \max(0, G + A_i - B_i)\). However, since \(A_i\) can be large, you need to temporarily compute using long long type to prevent overflow.

• Choosing block size \(B\): \(B \approx \sqrt{N}\) is a guideline, but adjust based on the balance between precomputation and query processing. In this code, \(B = 200\) is used.

• Memory optimization: Among the results in block_f, since the next stress value is less than \(K\), you can use short type or similar to reduce memory consumption.

  Source Code

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

using namespace std;

/**
 * Problem: Stress Meter
 * 
 * The task is to process a sequence of tasks, each with a load (A_i) and a recovery (B_i).
 * Stress G is updated as G = max(0, G + A_i - B_i).
 * If G >= K, the limit counter C is incremented and G is reset to 0.
 * We need to answer Q queries, each asking for the final (C, G) after processing a range [L, R].
 * 
 * Constraints: N, Q <= 6 * 10^4, K <= 300.
 * 
 * Since K is small, we can use square root decomposition to process queries efficiently.
 * Divide the tasks into blocks of size B. For each block, precompute the outcome (count, final_g)
 * for every possible initial stress g in [0, K-1].
 */

const int MAXN = 60005;
const int MAXK = 305;
const int B = 200; // Block size for square root decomposition

int A[MAXN], B_task[MAXN];

struct Result {
    int count;
    short next_g;
};

// Precomputed results for each block and each possible starting stress g
Result block_f[MAXN / B + 5][MAXK];

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

    int N, K, Q;
    if (!(cin >> N >> K >> Q)) return 0;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i] >> B_task[i];
    }

    // Precompute block results
    int num_blocks = (N + B - 1) / B;
    for (int b = 0; b < num_blocks; ++b) {
        int l = b * B + 1;
        int r = min((b + 1) * B, N);
        for (int g_start = 0; g_start < K; ++g_start) {
            int g = g_start;
            int c = 0;
            for (int i = l; i <= r; ++i) {
                // Apply task i logic:
                // Step 1 & 2: G = max(0, G + A_i - B_i)
                // Step 3: If G >= K, G = 0, C++
                long long next_g = (long long)g + A[i] - B_task[i];
                if (next_g >= K) {
                    c++;
                    g = 0;
                } else {
                    g = (next_g < 0) ? 0 : (int)next_g;
                }
            }
            block_f[b][g_start].count = c;
            block_f[b][g_start].next_g = (short)g;
        }
    }

    // Process queries
    for (int q = 0; q < Q; ++q) {
        int L, R;
        cin >> L >> R;
        int g = 0;
        int c = 0;
        int start_block = (L - 1) / B;
        int end_block = (R - 1) / B;

        if (start_block == end_block) {
            // L and R are in the same block, process tasks individually
            for (int i = L; i <= R; ++i) {
                long long next_g = (long long)g + A[i] - B_task[i];
                if (next_g >= K) {
                    c++;
                    g = 0;
                } else {
                    g = (next_g < 0) ? 0 : (int)next_g;
                }
            }
        } else {
            // Process tasks from L to the end of its block
            int first_block_end = (start_block + 1) * B;
            for (int i = L; i <= first_block_end; ++i) {
                long long next_g = (long long)g + A[i] - B_task[i];
                if (next_g >= K) {
                    c++;
                    g = 0;
                } else {
                    g = (next_g < 0) ? 0 : (int)next_g;
                }
            }
            // Process full blocks in between
            for (int b = start_block + 1; b < end_block; ++b) {
                c += block_f[b][g].count;
                g = block_f[b][g].next_g;
            }
            // Process tasks from the start of R's block to R
            int last_block_start = end_block * B + 1;
            for (int i = last_block_start; i <= R; ++i) {
                long long next_g = (long long)g + A[i] - B_task[i];
                if (next_g >= K) {
                    c++;
                    g = 0;
                } else {
                    g = (next_g < 0) ? 0 : (int)next_g;
                }
            }
        }
        // Output the result for the query
        cout << c << " " << g << "\n";
    }

    return 0;
}

---

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