#1380. PAVESEQ - Trung bình không nhỏ hơn P

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho dãy số nguyên a_1, a_2,…,a_n và một số nguyên dương P .

Yêu cầu: Đếm số dãy con liên tiếp khác nhau có trung bình cộng lớn hơn hoặc bằng P .

Dữ liệu vào:

  • Dòng đầu chứa số nguyên n\ (1≤n≤10^6) ;
  • Dòng hai chứa n số nguyên a_1, a_2,…,a_n\ (0≤a_i≤10^9) ;
  • Dòng cuối chứa một số nguyên dương P\ (0≤P≤10^9) .

Dữ liệu ra:

  • Ghi một số nguyên không âm duy nhất là kết quả tìm được.

Ví dụ:

Dữ liệu vào:
3
1 3 2
2
Dữ liệu ra:
5

Giải thích: Trong ví dụ trên, có 5 dãy con liên tiếp thỏa mãn là: [1, 2], [1,3], [2,2], [2,3], [3,3] .

Giới hạn:

  • Subtask \#1: 30\% tổng số điểm có n≤100 .
  • Subtask \#2: 30\% tổng số điểm tiếp theo có 101<n≤10^4 ;
  • Subtask \#3: 40\% tổng số điểm còn lại có 1001<n≤10^6 .