DÃY CON

Mỗi dãy con được gọi là dãy con liên tiếp nếu dãy con đó có dạng ~ a_i, a_{i+1}, a_{i+2}, …, a_j ~ với ~ 1≤i≤j≤n ~, là dãy con của dãy a gồm ~ n ~ phân tử cho trước.

Cho một dãy gồm ~ n ~ số nguyên dương ~ a_1, a_2, …, a_n ~ và hai số nguyên dương ~ p, q ~. Người ta muốn đếm số các dãy con liên tiếp của dãy số đã cho có tổng các số lớn hơn hoặc bằng ~ p ~ và nhỏ hơn hoặc bằng ~ q. ~

Yêu cầu: Hãy lập trình đếm số các dãy con liên tiếp thỏa mãn điều kiện bài toán.

Dữ liệu vào:

  • Dòng đầu ghi ba số nguyên ~ n, p,q~ ~(1≤n≤10^5;1≤p,q≤10^{18},p<q;) ~
  • Dòng thứ hai ghi ~n~ số nguyên ~ a_1, a_2, …, a_n (1≤a_i≤1000, i=1, 2, …,n) ~;

Kết quả:

  • Ghi một số nguyên là số các dãy con liên tiếp thỏa mãn có tổng các số lớn hơn hoặc bằng ~ p ~ và nhỏ hơn hoặc bằng ~ q ~.

Ví dụ:

Input 1:

1 1 2
1 
Output 1:
1 
Input 2:
6 5 10
3 2 4 2 1 2 
Output 2:
9 
Input 3:
12 20 35
5 4 6 4 3 4 11 2 14 5 9 3 
Output 4:
19 
Giải thích

  • Từ test ví dụ 2: Ta có các dãy con thỏa mãn là: (3, 2); (2, 4); (4, 2); (3, 2, 4); (2, 4, 2); (4, 2, 1); (2, 1, 2); (2, 4, 2, 1); (4, 2, 1, 2).
  • Vậy kết quả 9 dãy con.

Ràng buộc:

  • Có 40% số test tương ứng 40% số điểm có ~ 1<n≤100,q≤10^9 ~;
  • Có 40% số test tương ứng 40% số điểm có ~ 100<n≤5000, q≤10^9 ~;
  • Có 20% số test tương ứng 20% số điểm thỏa ~ 5000<n≤10^5, q≤10^{18} ~;

Bạn cần đăng nhập để nộp bài

hpcode.edu.vn
Code tích cực
Trong 24h
  1. quechi (19/21)
  2. nkhoinguyen (14/19)
  3. dangphong3108 (11/14)
Trong 7 ngày
  1. dangphong3108 (35/52)
  2. ducdung192 (21/41)
  3. celebi_276 (20/45)
Trong 30 ngày
  1. manhooh (124/294)
  2. bach2015 (82/168)
  3. thanhminh255 (81/144)
Thống kê
AC/Sub: 97887/180710
Pascal: 17121
C++: 130348
Python: 33199
Lượt xem/tải tests: 38609

Lưu Hải Phong - 2020
[email protected]