Tổng dãy con

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

Small

Dạng bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên gồm n phần tử \(a_1,a_2,\cdots,a_n\) \((|a_i| \leq 10^9)\). Cho giá trị \(x\) và \(q\) câu hỏi có dạng \(S(u,v)\). Với \(S(u,v)\) là tổng các giá trị của các phần tử từ \(u\) đến \(v\).

Yêu cầu: Đếm xem trong \(q\) câu hỏi đó có bao câu hỏi có giá trị nhỏ hơn \(x\).

Input

Dòng đầu tiên chứa ba số nguyên dương \(n,x,q (x \leq 10^9,q \leq 10^5)\).
Dòng thứ hai chứa \(a_1,a_2,\cdots,a_n (|a_i| \leq 10^9)\).
\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u,v (1 \leq u \leq v \leq n)\).

Output

In ra một số nguyên là số lượng câu hỏi có giá trị nhỏ hơn \(x\)

Scoring

Subtask \(1\) (\(50\%\) số điểm): \(n \leq 500\)
Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^4\)
Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^5\)

Example

Test 1

Input

Output

Note

\(S(2,3)=2+1=3<x=6\)
\(S(3,4)=1+6=7>x=6\)
\(S(5,5)=5<x=6\)
Vậy có 2 câu hỏi có giá trị nhỏ hơn \(x=6\)

Bình luận

summary

detail

#include <bits/stdc++.h>
#define v vector
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
char el = '\n';

int main(){
    ll n, x, q, cnt = 0;
    cin >> n >> x >> q;
    v<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    v<ll> p = {0};
    for (int i = 1; i <= n; i++) {
        p.push_back(a[i - 1] + p[i - 1]);
    }
    // for (int i = 0; i <= n; i++) {
    //  cout << p[i] << " ";
    // }

    for (int i = 0; i < q; i++){
        ll u, v;
        cin >> u >> v;
        if (p[v] - p[u - 1] < x){
            cnt++;
        }
    }
    cout << cnt;

    return 0;
}

Phản hồi

10 bình luận nữa