Bài 1 của đề /ckfinder/userfiles/files/TEST2.pdf
Cho dãy số gồm 𝑛 số nguyên 𝑎1, 𝑎2, . . , 𝑎𝑛 và hai số nguyên không âm 𝐿, 𝑅 (𝐿 ≤ 𝑅).
Yêu cầu: Đếm số cặp chỉ số (𝑖,𝑗) thỏa mãn điều kiện: 𝑖 ≤ 𝑗 và 𝐿 ≤ |𝑎𝑖 + 𝑎𝑖+1+. . +𝑎𝑗 | ≤ 𝑅.
Dữ liệu vào
- Dòng đầu chứa 3 số nguyên 𝑛, 𝐿, 𝑅 (0 < 𝑛 ≤ 105 ; 0 ≤ 𝐿 ≤ 𝑅 ≤ 109)
- Dòng thứ hai gồm 𝑛 số nguyên 𝑎1, 𝑎2, . . , 𝑎𝑛 (|𝑎𝑖 | ≤ 109 ). Hai số liên tiếp trên một dòng cách nhau một dấu cách.
Kết quả
- Gồm một dòng chứa một số là số cặp chỉ số (𝑖,𝑗) đếm được.
input
3 0 1
1 -1 2
output
4
Giải thích: Có 4 cặp chỉ số thỏa mãn là: (1,1); (1,2); (2,2); (2,3)
Giới hạn: Có 50% số test có 𝑛 ≤ 1000
Nguồn: 3D '1819