Phủ Sóng 5G Trên Quốc Lộ 1A

Mô tả

Dọc tuyến Quốc Lộ 1A, MobiFone lắp đặt n trạm phát sóng 5G liên tiếp. Mỗi trạm có giá trị công suất đo được (tính bằng watt), có thể mang dấu dương (phát sóng mạnh) hoặc âm (nhiễuDoing thuật toán suy hao). Một đoạn tuyến từ trạm L đến trạm R được xem là đạt chuẩn khi tổng công suất của các trạm trong đoạn đó lớn hơn hoặc bằng ngưỡng an toàn k watt.

Trung tâm vận hành mạng cần thống kê số lượng đoạn tuyến liên tục đạt chuẩn để ưu tiên bảo trì, cấp thêm băng thông.

Đầu vào

• Một mảng số nguyên a gồm n phần tử, a[i] là công suất của trạm thứ i.
• Một số nguyên k là ngưỡng công suất an toàn.

Đầu ra

• Trả về một số nguyên là tổng số lượng cặp đoạn [L, R] (với 0 <= L <= R < n) mà tổng các phần tử từ a[L] đến a[R] lớn hơn hoặc bằng k.

Ràng buộc

• 1 <= n <= 10^5
• -10^4 <= a[i] <= 10^4
• -10^9 <= k <= 10^9
• Tổng công suất của cả dãy nằm trong khoảng [-10^9, 10^9].

Ví dụ

Ví dụ 1:

• Đầu vào: [1, 2, 3, 4, 5], 5
• Đầu ra: 10

Giải thích: Có 10 đoạn có tổng >= 5. Các đoạn đạt chuẩn: [3,4] (tổng 7), [2,3,4] (tổng 9), [1,2,3,4] (tổng 10), [0,1,2,3,4] (tổng 15), [4] (tổng 5), [3,4] đã tính, [2,3,4] đã tính, [1,2,3,4] đã tính, [0..4] đã tính, [2,3,4,5] (tổng 14), [1,2,3,4,5] (tổng 15), [0,1,2,3,4,5] (tổng 21), [4,5] (tổng 9), [3,4,5] (tổng 12), [2,3,4,5] (tổng 14), [1,2,3,4,5] (tổng 15), [0,1,2,3,4,5] (tổng 21). Cụ thể: [3,4]=7, [2,3,4]=9, [1,2,3,4]=10, [0..4]=15, [4,5]=9, [3,4,5]=12, [2..5]=14, [1..5]=15, [0..5]=21, và [4]=5. Tổng cộng 10 đoạn.