USACO 2011 - Nov - Gold - Above the Median

View as PDF

Submit solution


Points: 0.42 (partial)
Time limit: 0.52s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=91
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bác nông dân John đã xếp ~N~ ~(1 \le N \le 100\,000)~ chú bò của bác để đo chiều cao của chúng; chú bò thứ ~i~ có chiều cao là ~H_i~ ~(1 \le H_i \le 1\,000\,000\,000)~ nanomét. Bác muốn chụp ảnh một đoạn con liên tiếp các chú bò để gửi đến cuộc thi ảnh cho bò ở hội chợ tỉnh.

Hội chợ có một luật rất kì quái về các bức ảnh được nộp: một bức ảnh chỉ được tính là hợp lệ nếu dãy bò trong bức ảnh có chiều cao trung vị đạt ngưỡng thấp nhất là ~X~ ~(1 \le X \le 1\,000\,000\,000)~.

Trong bài này, ta định nghĩa trung vị của một mảng ~A[0 \ldots K]~ là ~A\left[\lceil\frac{K}{2}\rceil\right]~ với ~A~ đã được sắp xếp, với ~\lceil\frac{K}{2}\rceil~ là ~\frac{K}{2}~ làm tròn lên đến số nguyên gần nhất (hay là chính ~\frac{K}{2}~, nếu ~\frac{K}{2}~ đã là một số nguyên). Ví dụ trung vị của ~[7, 3, 2, 6]~ là ~6~, trung vị của ~[5, 4, 8]~ là ~5~.

Hãy giúp bác John đếm số lượng dãy con liên tiếp khác nhau các chú bò của bác mà bác có thể chụp để gửi đến cuộc thi chụp ảnh.

Input

  • Dòng ~1~: Hai số nguyên ~N~ và ~X~ cách nhau bởi một dấu cách.
  • Dòng ~2 \ldots N+1~: Dòng ~i+1~ chứa số nguyên ~H_i~.

Output

  • Dòng ~1~: Số lượng dãy con liên tiếp khác nhau các chú bò của bác John mà có trung vị ít nhất là ~X~. Lưu ý số này có thể vượt quá giới hạn của số nguyên 32-bit.

Sample Input

4 6 
10 
5 
6 
2

Sample Output

7

Comments

Please read the guidelines before commenting.


There are no comments at the moment.