概要

\(N\) 個のタスクを順番に処理したときの「限界に達した回数 \(C\)」と「最終的なストレス値 \(G\)」を求めるクエリに \(Q\) 回答える問題です。ストレス値がしきい値 \(K\) 以上になるとリセットされるという特性と、\(K\) が比較的小さい（\(K \leq 300\)）という点を利用して効率的に解く必要があります。

考察

素直なシミュレーションの問題点

各クエリに対して、指定された範囲 \([L, R]\) のタスクを一つずつシミュレーションすると、1クエリあたり最悪 \(O(N)\) かかります。全体で \(O(QN)\) となり、今回の制約（\(N, Q \leq 6 \times 10^4\)）では実行時間制限に間に合いません。

重要な観察：\(K\) の小ささ

ストレス値 \(G\) は、ステップ 3 の処理が終わった時点では必ず \(0 \leq G < K\) の範囲に収まります。 \(K\) が最大 300 と非常に小さいため、「ある時点でのストレス値 \(G\) が分かれば、その後の挙動は一意に決まり、その状態数は \(K\) 通りしかない」という点に着目します。

解決策：平方分割

タスクの列をサイズ \(B\) ごとのブロックに分割する平方分割を導入します。 各ブロックについて、以下の値を前計算しておきます。 - そのブロックの開始時のストレス値が \(g \in [0, K-1]\) だったとき、 - ブロック内のタスクをすべて処理した後のストレス値はいくらか？ - そのブロック内で何回限界に達したか？

これにより、クエリの範囲内にある「まるごと含まれるブロック」については、シミュレーションをスキップして前計算した結果を足し合わせるだけで済むようになります。

アルゴリズム

1. 前計算

1. \(N\) 個のタスクをサイズ \(B\)（例：200程度）のブロックに分けます。
2. 各ブロック \(b\) について、初期ストレス \(g = 0, 1, \ldots, K-1\) のそれぞれに対し、ブロック内のタスクをシミュレーションします。
3. 結果（最終的な \(g\) と限界到達回数 \(c\)）を block_f[block_id][initial_g] に保存します。

2. クエリ回答

クエリ \([L, R]\) に対して以下の手順で計算します。 1. 左端の端数部分: \(L\) から「\(L\) が属するブロックの右端」まで、一つずつ愚直にシミュレーションします。 2. 中間の完全なブロック: \(L\) の次のブロックから \(R\) の直前のブロックまで、前計算した block_f を使って \(G\) と \(C\) を一気に更新します。 3. 右端の端数部分: 「\(R\) が属するブロックの左端」から \(R\) まで、一つずつ愚直にシミュレーションします。 ※ \(L\) と \(R\) が同じブロックにある場合は、全体を愚直にシミュレーションします。

計算量

\(B\) をブロックサイズとします。

• 前計算: \(O(\frac{N}{B} \cdot B \cdot K) = O(NK)\)
  • ブロック数 \(\frac{N}{B}\)、各ブロック内で \(K\) 通りの初期値に対し、サイズ \(B\) のシミュレーションを行います。
• クエリ: \(O(Q \cdot (B + \frac{N}{B}))\)
  • 端数のシミュレーションに最大 \(2B\)、ブロックのジャンプに最大 \(\frac{N}{B}\) かかります。

全体の計算量は \(O(NK + Q(B + \frac{N}{B}))\) です。 \(N, Q = 6 \times 10^4, K = 300, B = 200\) とすると、前計算が約 \(1.8 \times 10^7\)、クエリ処理が約 \(3 \times 10^7\) 程度となり、制限時間内に十分収まります。

実装のポイント

• ストレス値の更新式: ステップ 1 と 2 は \(G = \max(0, G + A_i - B_i)\) とまとめられます。ただし、\(A_i\) が大きいため、一時的に long long 型で計算してオーバーフローを防ぐ必要があります。

• ブロックサイズ \(B\) の選択: \(B \approx \sqrt{N}\) が目安ですが、前計算とクエリのバランスを見て調整します。このコードでは \(B = 200\) としています。

• メモリ節約: block_f の結果のうち、次のストレス値は \(K\) 未満なので short 型などを使うとメモリ消費を抑えられます。

  ソースコード

#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;
}

---

この解説は gemini-3-flash-thinking によって生成されました。