Vudu
레이팅 미적용의견: 0
\(2^{th}\) round, November \(7^{th}\) 2015
Young Mirko has been buying voodoo dolls lately. Considering that he is very interested in the cheapest
purchase possible, he has been tracking the prices of voodoo dolls each day. His price list consists of
doll prices in the last \(N\) days, where doll price \(a\)\(i\) represents the price of a doll \(i\) days ago.
Mirko thinks he has noticed a connection between the average doll price in a sequence of consecutive
days and the price on the following day. He wants to test his hunch and is puzzled by a very interesting
question: “For a given \(P\), how many different consecutive subsequences in the last \(N\) days are there,
when the average doll price was greater than or equal to \(P\)?”
Two consecutive subsequences are considered different if their beginnings or ends are different.
In test cases worth 30% of points the sequence length \(N\) will be less than or equal to 10 000.
The first line of input contains the integer \(N\), the sequence length (1 ⩽\(N\) ⩽1 000 000).
The second line of input contains \(N\) prices \(a@@RISE_MATH_BLOCK_0@@i\) ⩽1 000 000 000).
The third line of input contains an integer \(P\). (0 ⩽\(P\) ⩽1 000 000 000).
The first and only line of output must contain the answer to Mirko’s question for a given \(P\).
3
1 2 3
3
3
1 3 2
2
3
1 3 2
3output
output
1
5
1Clarification of the first example: The only subsequence that has an average greater than or equal to 3 is
{3}.
Clarification of the second example: The subsequences that have an average greater than or equal to 2
are {1, 3}, {1, 3, 2}, {3}, {3, 2}, {2}.
평가 및 의견
Vudu
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Vudu