DÃY CHỨA MAX
Xem dạng PDF
Gửi bài giải
Điểm:
100,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
nummax.inp
Output:
nummax.out
Nguồn bài:
Dạng bài
Máy chấm
Alisa Mikhailovna Kujou, Kanade Yoisaki
Xét dãy số nguyên ~A=(a_1,a_2,\dots,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.
Yêu cầu: 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:
Vào từ file văn bản NUMMAX.INP gồm:
- 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,\dots,a_n~ ~(1 \le a_i \le 10^9;\forall i \in [1;n])~
Output:
Ghi ra file văn bản NUMMAX.OUT một số nguyên duy nhất là số lượng dãy con tìm được.
Ví dụ:
NUMMAX.INP
4 5
1 3 5 2
NUMMAX.OUT
6
Subtask:
- Có ~20\%~ số test tương ứng ~20\%~ số điểm có ~n \le 10^3~ và không có dãy con thỏa mãn.
- Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 10^3~, đồng thời số ~b~ xuất hiện đúng ~1~ lần trong dãy và là số lớn nhất trong dãy đó.
- Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 5.10^3~
- ~40\%~ số test còn lại tương ứng ~40\%~ số điểm không có ràng buộc gì thêm.
Bình luận
set + tknp 🐧