USACO 2011 - Nov - Gold - Above the Median

Xem dạng PDF

Gửi bài giải


Điểm: 0,42 (OI)
Giới hạn thời gian: 0.52s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
http://www.usaco.org/index.php?page=viewproblem2&cpid=91
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -6
    daicaphugiao  đã bình luận lúc 6, Tháng 3, 2024, 15:28

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -2
    VVUU  đã bình luận lúc 6, Tháng 3, 2024, 15:18

    Không biết làm đừng đọc sol nhá <3