#1193. AVERTREE - Chiều cao trung bình của cây

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: Trùm CUỐI

Đề bài

Nguồn: Ôn Thầy Hiếu Hưng Yên - T11/2019

Sau khi trúng thầu khai thác đất ven đường toàn huyện, Phú Ông giao cho Bờm trồng và chăm sóc N cây dọc con đường chạy từ làng lên trung tâm. Hết một năm chăm sóc, chiều cao hiện tại của các cây theo thứ là h_1,h_2,h_3,…h_n . Để đánh giá hiệu quả làm việc, Phú Ông đưa ra tiêu chí và chọn một đoạn các cây liên tiếp để khảo sát. Nếu đoạn các cây đó có chiều cao trung bình lớn hơn hoặc bằng k , Phú Ông sẽ thưởng cho Bờm cả tháng lương. Bờm có nhiệm vụ đưa ra cho Phú Ông một số lựa chọn các đoạn để Phú Ông khảo sát.

Yêu cầu: Hãy giúp Bờm xác định có bao nhiêu đoạn cây liên tiếp có giá trị chiều cao trung bình lớn hơn hoặc bằng k .

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên dương n, k ;
  • Dòng thứ hai chứa n số nguyên dương h_1,h_2,h_3,…,h_n\ (1≤h_i≤10^9) .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số lượng đoạn tìm được.

Ví dụ:

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

Giới hạn:

  • 30\% số test có n≤5000;h_i≤10^9 ;
  • 25\% số test khác có n≤10^5; k,h_i≤2 ;
  • 45\% số test còn lại có n≤10^5;k≤10^9 .