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 
5 6 3
7 2 1 6 5
2 3
3 4
5 5
Output 
2
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

  • Sangnguyen • 6:57 p.m. 29 Tháng 3, 2025 •

    include<bits/stdc++.h>

    define ll long long

    using namespace std;

    int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
    ll n;ll x;int q;cin>>n>>x>>q;
    ll kq,dem=0;
    vector<ll> a(n+1);
    vector<ll> b(n+1,0);
    for(int i=1;i<=n;i++){
    cin>>a[i];
    b[i]=b[i-1]+a[i];
    }
    for(int i=0;i<q;i++){ ll u,v; cin>>u>>v;
    kq=b[v]-b[u-1];
    if(kq<x)dem++;
    }
    cout<<dem;
    }

    0
    Phản hồi
      • 10 bình luận nữa