Đếm số dương
Xem dạng PDF
Gửi bài giải
Điểm:
20,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho dãy ~𝐴~ gồm ~𝑛~ số nguyên dương ~𝑎_1, 𝑎_2, . . , 𝑎_𝑛~. Cho ~𝑞~ truy vấn có dạng ~𝑙~, ~𝑟~
Yêu cầu: Với mỗi truy vấn ~𝑙~, ~𝑟~ hãy đếm số lượng các số có giá trị dương từ phần tử thứ ~l~ đến phần tử thứ ~r~ của dãy số ~A~.
Dữ liệu vào:
- Dòng thứ nhất ghi 2 số nguyên dương ~𝑛~ và ~𝑞~ (~1 ≤ 𝑛,𝑞 ≤ 2.10^6~)
- Dòng thứ hai ghi ~𝑛~ số nguyên ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~ các số có giá trị tuyệt đối không vượt quá ~10^6~
- ~𝑞~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~𝑙~, ~𝑟~ (~1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛~)
Dữ liệu ra:
- ~𝑞~ dòng mỗi dòng ghi một số nguyên dương là kết quả tìm được của mỗi truy vấn.
Ví dụ
Input
9 3
1 -3 8 9 -7 -9 9 7 -1
1 6
2 7
6 9
Output
3
3
2
Bình luận
include<bits/stdc++.h>
using namespace std; long long pre[2000004],n,q,x,l,r; int main () { iosbase::syncwith_stdio(false); cin.tie(NULL); cin>>n>>q;for(int i=1;i<=n;++i) {cin>>x;if(x>0)pre[r]=pre[i-1]+1; else pre[i]=pre[i-1];} {cin>>l>>r; cout<<pre[i]-pre[l-1]<<'\n';} }
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.