Trại hè Hùng Vương 2019 - Dãy chứa max
Xem dạng PDF
Gửi bài giải
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Điểm:
25,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Dạng bài
Ngôn ngữ cho phép
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
Xét dãy số nguyên ~A = (a_1, a_2, ..., a_n)~. Dãy chứa các phần tử ở các vị trí liên tiếp của ~A~ được gọi là dãy con. Hai dãy con được gọi là khác nhau nếu tồn tại ít nhất một vị trí mà phần tử của ~A~ ở vị trí đó tham gia vào dãy con này và không tham gia vào dãy con kia.
Cho số nguyên ~b~. Hãy xác định số lượng dãy con có giá trị lớn nhất của các phần tử trong dãy con đúng bằng ~b~.
Input
- Dòng đầu tiên chứa hai số nguyên ~n~ và ~b~ (~2 \le n \le 10^5, 1 \le b \le 10^9~).
- Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9, i = 1 \dots n~).
Output
- Đưa ra một số nguyên duy nhất là số lượng dãy con tìm được.
Sample Input 1
4 5
1 3 5 2
Sample Output 1
6
Subtasks
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20~ | ~n \le 10^3~ và không có dãy con thỏa mãn. |
| 2 | ~20~ | ~n \le 10^3~, đồng thời số ~b~ xuất hiện đúng ~1~ lần và là số lớn nhất trong dãy. |
| 3 | ~20~ | ~n \le 5 \times 10^3~. |
| 4 | ~40~ | Không có ràng buộc bổ sung gì thêm. |
Bình luận