← 返回题目列表

AtCoder · arc075_c

E. 有意义的意思

中文机器翻译题面 查看原题

分数: 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