Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
KMEDIAN - Above the Median |
Farmer John has lined up his N (1 ≤ N ≤ 100,000) cows in a row to measure their heights; cow i has height H_i (1 ≤ H_i ≤ 1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair.
The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 ≤ X ≤ 1,000,000,000).
For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.
Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.
Input
- Line 1: Two space-separated integers: N and X.
- Lines 2..N+1: Line i+1 contains the single integer H_i.
Output
- Line 1: The number of subsequences of FJ's cows that have median at least X. Note this may not fit into a 32-bit integer.
Example
Input:
4 6
10
5
6
2
Output:
7
Explain: There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.
Được gửi lên bởi: | khanhptnk |
Ngày: | 2011-11-19 |
Thời gian chạy: | 0.302s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED |
Nguồn bài: | USACO November 2011 |
hide comments
2021-05-27 18:01:12
Tham khảo: https://vnspoj.github.io/problems/KMEDIAN |
|
2019-06-08 19:08:39
sao k chạy dịch lỗi nhể =(( làm AC ngay phát đầu cảm giác nó khác khác, khó khó chịu =(( |
|
2019-06-08 19:07:35
1 đấm AC :(( |
|
2017-06-26 09:46:46
sao bài này không bị hidden. |
|
2016-05-14 06:42:21
oh shit khai báo thiếu mảng :v |
|
2016-04-18 11:25:25
Bách yêu Khánh Lâm |
|
2016-04-18 09:35:54
Last edit: 2016-04-18 11:01:59 |
|
2015-09-05 15:20:55
Tham khảo lời giải tại http://vnspoj.blogspot.com/p/blog-page_7.html |
|
2015-08-02 09:03:06 N�ng D�n John
Vật vã, hichic !!! [nongdanjohn] |
|
2015-08-01 17:22:09 N�ng D�n John
==)))))) |