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
    • masara815 • 2:40 p.m. 27 Tháng 2, 2025 •

      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;
}
      0
      Phản hồi
      • P1A1DangThaiCanh • 8:33 a.m. 23 Tháng 11, 2024 •

        giống chatgpt quá

        -3
        Phản hồi
        • dackhoatvd2015 • 4:26 p.m. 29 Tháng 10, 2024 •

          cái này học thầy nhỏ, ko phải chatgpt

          2
          Phản hồi
          • dackhoatvd2015 • 6:35 p.m. 28 Tháng 10, 2024 •

            1
            Phản hồi
            • dackhoatvd2015 • 6:33 p.m. 28 Tháng 10, 2024 •

              n, x, q = map(int, input().split())
              arr = list(map(int,input().split()))
              prefix_sum = [0] * (n + 1)
              for i in range(1, n + 1):
              prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
              cnt = 0
              for _ in range(q):
              l, r = map(int, input().split())
              tong = prefix_sum[r] - prefix_sum[l-1]
              if tong < x:
              cnt += 1
              print(cnt)

              1
              Phản hồi
              • dackhoatvd2015 • 6:31 p.m. 28 Tháng 10, 2024 •

                chúc mn làm tốt

                2
                Phản hồi
                • dackhoatvd2015 • 6:30 p.m. 28 Tháng 10, 2024 • ← đã chỉnh sửa

                  n, x, q = map(int, input().split())
                  arr = list(map(int,input().split()))
                  prefix_sum = [0] * (n + 1)
                  for i in range(1, n + 1):
                  prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
                  cnt = 0
                  for _ in range(q):
                  l, r = map(int, input().split())
                  tong = prefix_sum[r] - prefix_sum[l-1]
                  if tong < x:
                  cnt += 1
                  print(cnt)

                  1
                  Phản hồi
                  • dackhoatvd2015 • 6:30 p.m. 28 Tháng 10, 2024 •

                    dễ mà

                    1
                    Phản hồi
                    • Duykhoi1009 • 4:03 p.m. 27 Tháng 10, 2024 •

                      cho code python đi

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