#P2717. 寒假作业

    ID: 3515 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>树状数组cdq 分治

寒假作业

背景

zzs 和 zzy 正在被寒假作业折磨,然而他们有答案可以抄啊。

题目描述

他们共有 nn 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 aia_i,表示抄这个作业所要花的精力。

zzs 现在想要知道,有多少组连续的寒假作业的疲劳值的平均值不小于 kk?

简单地说,给定一个长度为 nn 的正整数序列 {ai}\{a_i\},求出有多少个连续子序列的平均值不小于 kk。

输入格式

第一行是两个整数,分别表示序列长度 nn 和给定的参数 kk。

接下来有 nn 行,每行一个整数,第 ii 个整数表示序列的第 ii 个数字 aia_i。

输出格式

输出一行一个整数表示答案。

3 2
1
2
3

4

提示

样例 1 解释

共有 66 个连续的子序列,分别是 (1)(1)、(2)(2)、(3)(3)、(1,2)(1,2)、(2,3)(2,3)、(1,2,3)(1,2,3),平均值分别为 11、22、33、1.51.5、2.52.5、22,其中平均值不小于 22 的共有 44 个。

数据规模与约定

  • 对于 20%20\% 的数据,保证 n≤100n \leq 100。
  • 对于 50%50\% 的数据,保证 n≤5000n \leq 5000。
  • 对于 100%100\% 的数据,保证 1≤n≤1051 \leq n \leq 10^5,1≤ai,k≤1041 \leq a_i,k \leq 10^4。