分数: 600 点
问题陈述
给你一个长度的整数序列 N, a = {a_1, a_2, …, a_N},和一个整数 K.
a 有 N(N+1)/2 非空连续子序列,{a_l, a_{l+1}, …, a_r} (1 ≤ l ≤ r ≤ N)。其中算术平均值大于等于的有多少个 K?
约束
- 所有输入值均为整数。
- 1 ≤ N ≤ 2 \times 10^5
- 1 ≤ K ≤ 10^9
- 1 ≤ a_i ≤ 10^9
输入
输入由标准输入按以下格式给出:
N K a_1 a_2 : a_N
输出
打印算术平均值大于或等于的非空连续子序列的数量 K.
示例输入 1
3 6 7 5 7
示例输出 1
5
的所有非空连续子序列 a 列出如下:
- {a_1} = {7}
- {a_1, a_2} = {7, 5}
- {a_1, a_2, a_3} = {7, 5, 7}
- {a_2} = {5}
- {a_2, a_3} = {5, 7}
- {a_3} = {7}
他们的手段是 7, 6, 19/3, 5, 6 和 7,其中五个是 6 或更大。请注意{a_1} 和 {a_3} 无法通过其元素的值来区分,但我们单独对它们进行计数。
示例输入 2
1 2 1
示例输出 2
0
示例输入 3
7 26 10 20 30 40 30 20 10
示例输出 3
13