Tổng dãy con
Xem PDF
Đ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
2Note
- \(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
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)
7 bình luận nữa