Chọn ĐTQG An Giang 2025 - INTERVAL
Xem dạng PDF
Gửi bài giải
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho dãy ~a~ gồm ~n~ số nguyên không âm và một số nguyên không âm ~K~. Đếm số lượng cặp ~(i,j)~ thỏa mãn:
~1 \le i \le j \le n~.
~a_i + \min(a_i,a_{i+1},\dots,a_j) - a_j \le K~.
Input
Dòng đầu tiên có hai số nguyên ~n~ và ~K~ ~(1 \le n \le 10^5)~; ~(K \le 10^{12})~.
Dòng thứ hai có ~n~ số nguyên ~a_1,a_2,\dots,a_n~ ~(a_i \le 10^{12})~.
Output
Một số nguyên duy nhất – số lượng cặp ~(i,j)~ thỏa mãn.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~n \le 5000~. |
| 2 | ~30\%~ | ~a_i~ phân biệt. |
| 3 | ~30\%~ | ~a_i \le 10^6~. |
| 4 | ~10\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
5 10
15 10 3 4 8
Sample Output 1
11
Bình luận