#819. NUMMAX - Dãy chứa max

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

TRẠI HÈ HÙNG VƯƠNG LẦN THỨ XⅤ (SƠN LA 2019)

Xét dãy số nguyên A=\left(a_1,a_2,...,a_n\right) . 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 .

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên n b\ \left(2≤n≤10^5,1≤b≤10^9\right)
  • Dòng thứ hai chứa n số nguyên a_1,a_2,...,a_n\ \left(1≤a_i≤10^9,i=1÷n\right)

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số lượng dãy con tìm được.

Ví dụ:

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

Ràng buộc:

  • 20\% số test tương ứng 20\% số điểm có n≤10^3 và không có dãy con thỏa mãn.
  • 20\% số test khác tương ứng 20\% số điểm có n≤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 đó.
  • 20\% số test khác tương ứng 20\% số điểm có n≤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.