Submission #73780099

---

Source Code Expand

#ifdef LOCAL
#include "comet/debug.hpp"
#else
#define debug(...) (void)0
#endif

#include <iostream>
#include <cassert>
using namespace std;


int N, Q, ans[2 << 17];
long long K, A[2 << 17], sans[2 << 17];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> K >> Q;
    
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    
    for (int i = 1; i <= N; i++) {
        ans[i] = 0;
    }
    
    int cur = 1;
    long long weight = 0;
    for (int i = 1; i <= N; i++) {
        weight += A[i];
        while (weight > K) {
            ans[cur] = i;
            weight -= A[cur];
            cur++;
        }
    }
    while (cur <= N) {
        ans[cur] = N;
        cur++;
    }
    
    for (int i = 1; i <= N; i++) {
        assert(ans[i] >= i);
        sans[i] = (long long)sans[i - 1] + ans[i];
    }
    
    while (Q--) {
        int l, r;
        cin >> l >> r;
        cout << sans[r] - sans[l - 1] << '\n';
    }
    
    return 0;
}

Submission Info

Judge Result