trang chủ / đề bài / thhv15_aseq

Dãy số

Đề bài

Mô tả

Cho dãy số gồm n số nguyên a1,a2,…,an và 2 số nguyên không âm L,R (L≤R).

Yêu cầu: Đếm số cặp chỉ số (i;j) thỏa mãn điều kiện i≤j và L≤|ai+ai+1+…+aj|≤R.

Dữ liệu vào

  • Dòng đầu chứa 3 số nguyên n,L,R (0<n≤105, 0≤L≤R≤109).
  • Dòng thứ hai ghi n số nguyên trong dãy số (|ai|≤109).

Dữ liệu ra

Một dòng duy nhất chứa số cặp chỉ số (i;j) tìm được.

Ràng buộc

  • 0<n≤105;
  • 0≤L≤R≤109;
  • |ai|≤109.
  • Có 50% số test ứng với 50% số điểm của bài có n≤1000.

Ví dụ

Input Output Giải thích
3 0 1
1 -1 2		 4 Các cặp thỏa mãn: (1;1) tổng 1, (2;2) tổng −1, (1;2) tổng 0, (2;3) tổng 1.
5 3 7
4 -9 2 3 -5		 9 Ví dụ bổ sung: các đoạn có tổng âm như (1;2) tổng −5 hay (2;3) tổng −7 cũng được đếm vì xét giá trị tuyệt đối.
4 0 0
2 -2 2 -2		 4 Ví dụ bổ sung: đếm các đoạn có tổng bằng 0: (1;2), (2;3), (3;4), (1;4).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0