Overview

This problem asks you to compute the stress value and the number of times the limit is reached after processing a subsequence \([L, R]\) of \(N\) tasks, for \(Q\) queries. By leveraging the fact that the stress value \(G\) always stays in the range \(0\) to \(K-1\), we can efficiently handle this using sqrt decomposition.

Analysis

Naive Approach

If we simulate tasks one by one from \(L\) to \(R\) for each query, the worst case is \(O(N)\) per query, giving \(O(NQ)\) overall. Since \(N, Q \leq 6 \times 10^4\), this results in up to \(3.6 \times 10^9\) operations, which causes TLE.

Key Observation: The State Space Is Small

Focus on the processing in Step 3. Since \(G\) is reset when \(G \geq K\), the stress value \(G\) after processing each task is always between \(0\) and \(K-1\). Since \(K \leq 300\), there are only \(300\) possible states.

Solution Idea

We divide the task sequence into blocks of size approximately \(\sqrt{N}\). For each block, we precompute “given that the starting stress value is \(g\) (\(0 \leq g < K\)), what are the resulting stress value and the number of times the limit is reached after processing the entire block?” This allows \(O(1)\) transitions per block.

Algorithm

Preprocessing

1. Divide the task sequence into blocks of \(\sqrt{N}\) tasks each.
2. For each block \(b\), for each starting stress value \(g = 0, 1, \ldots, K-1\), simulate all tasks in the block sequentially and record the following:
   • block_next[b][g]: the stress value after processing
   • block_count[b][g]: the number of times the limit was reached

Query Processing

For a query \([L, R]\), split the interval into three parts:

[L, ... end of left partial block] | [complete blocks] | [start of right partial block, ..., R]

1. Left partial block: Simulate tasks one by one (\(O(\sqrt{N})\))
2. Middle complete blocks: Use the precomputed results to transition in \(O(1)\) per block (\(O(\sqrt{N})\) blocks)
3. Right partial block: Simulate tasks one by one (\(O(\sqrt{N})\))

Concrete Example

With \(K = 5\), block size 3, and a block containing “\(A = [3, 2, 4],\ B = [1, 0, 3]\)”:

• Starting \(g=0\): \(0 \xrightarrow{+3-1} 2 \xrightarrow{+2-0} 4 \xrightarrow{+4-3} 5 \geq 5\) → reset → final \(g=0\), \(c=1\)
• Starting \(g=2\): \(2 \xrightarrow{+3-1} 4 \xrightarrow{+2-0} 6 \geq 5\) → reset → \(0 \xrightarrow{+4-3} 1\) → final \(g=1\), \(c=1\)

In this way, we precompute all \(K\) possible starting states.

Complexity

• Preprocessing time complexity: \(O(N \times K)\)
  • Number of blocks: \(\frac{N}{\sqrt{N}} = \sqrt{N}\), each block processes \(K\) initial values × block size \(\sqrt{N}\)
  • \(\sqrt{N} \times K \times \sqrt{N} = NK\)
• Query processing time complexity: \(O(Q \times \sqrt{N})\)
• Overall time complexity: \(O(NK + Q\sqrt{N})\)
  • For \(N = 6 \times 10^4, K = 300\): \(NK = 1.8 \times 10^7\), \(Q\sqrt{N} \approx 1.5 \times 10^7\)
• Space complexity: \(O(\sqrt{N} \times K + N)\)

Implementation Notes

• Overflow prevention: Since \(A_i\) can be up to \(10^9\), you need to use long long when computing \(G + A_i\). However, after Step 3, \(G < K \leq 300\), so int is sufficient for storing the state.

• Block size selection: Use sqrt(N), and handle remainders by adjusting the number of blocks.

• Queries within the same block: If \(L\) and \(R\) belong to the same block, simulate directly without using the precomputed data.

• Conversion to 0-indexed: Since the input is 1-indexed, we convert with L--; R--;.

  Source Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K, Q;
    cin >> N >> K >> Q;
    
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    
    int block_size = max(1, (int)sqrt(N));
    int num_blocks = (N + block_size - 1) / block_size;
    
    vector<vector<int>> block_next(num_blocks, vector<int>(K));
    vector<vector<int>> block_count(num_blocks, vector<int>(K));
    
    for (int b = 0; b < num_blocks; b++) {
        int start = b * block_size;
        int end = min(N, start + block_size);
        for (int g = 0; g < K; g++) {
            int cur_g = g;
            int cur_c = 0;
            for (int i = start; i < end; i++) {
                long long ng = (long long)cur_g + A[i];
                ng = max(0LL, ng - B[i]);
                if (ng >= K) {
                    cur_c++;
                    cur_g = 0;
                } else {
                    cur_g = (int)ng;
                }
            }
            block_next[b][g] = cur_g;
            block_count[b][g] = cur_c;
        }
    }
    
    for (int q = 0; q < Q; q++) {
        int L, R;
        cin >> L >> R;
        L--; R--;
        
        int cur_g = 0, cur_c = 0;
        
        int lb = L / block_size;
        int rb = R / block_size;
        
        if (lb == rb) {
            for (int i = L; i <= R; i++) {
                long long ng = (long long)cur_g + A[i];
                ng = max(0LL, ng - B[i]);
                if (ng >= K) {
                    cur_c++;
                    cur_g = 0;
                } else {
                    cur_g = (int)ng;
                }
            }
        } else {
            int left_end = (lb + 1) * block_size - 1;
            for (int i = L; i <= left_end; i++) {
                long long ng = (long long)cur_g + A[i];
                ng = max(0LL, ng - B[i]);
                if (ng >= K) {
                    cur_c++;
                    cur_g = 0;
                } else {
                    cur_g = (int)ng;
                }
            }
            for (int b = lb + 1; b < rb; b++) {
                cur_c += block_count[b][cur_g];
                cur_g = block_next[b][cur_g];
            }
            int right_start = rb * block_size;
            for (int i = right_start; i <= R; i++) {
                long long ng = (long long)cur_g + A[i];
                ng = max(0LL, ng - B[i]);
                if (ng >= K) {
                    cur_c++;
                    cur_g = 0;
                } else {
                    cur_g = (int)ng;
                }
            }
        }
        
        cout << cur_c << " " << cur_g << "\n";
    }
    
    return 0;
}

---

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