4143 - 区段分析

题目描述

某数据分析部门正在对一条数据序列进行研究。该序列由 N 个数据点组成,第 i 个数据点的数值为 A_i

为了进行统计分析,研究人员希望从这条序列中选取若干个 连续区段 进行评估。每个区段都会计算一个代表性指标——中位数,并与给定的标准值 X 进行比较。

本题中,中位数的定义如下:

  • 将区段内所有数值从小到大排序;
  • 若区段长度为奇数,中位数为正中间的那个数;
  • 若区段长度为偶数,中位数定义为 升序排序后靠右的中间值(即升序排序后最中间 2 个数的较大数)。

例如:

  • 数组 {7, 3, 2, 6} 排序后为 {2, 3, 6, 7},中位数为 6
  • 数组 {5, 4, 8} 排序后为 {4, 5, 8},中位数为 5

现在,研究人员给定一个阈值 X,希望统计:在所有连续区段中,中位数大于等于 X 的区段共有多少个。

请你编程完成这一统计任务。

输入

第一行包含两个整数 N, X,分别表示数据点个数和判定阈值。

接下来 N 行,每行一个整数,第 i 行表示第 i 个数据点的数值 A_i

输出

输出一个整数,表示中位数大于等于 X 的连续区段数量。

样例

输入

4 6
10
5
6
2

输出

7

输入

8 5
3
7
4
6
2
8
1
5

输出

26

输入

16 5
1
6
2
7
3
8
4
9
10
5
11
4
12
3
13
2

输出

120
说明

样例 1 说明

给定的数据序列为:10, 5, 6, 2

所有可能的连续区段共有 10 个,其中中位数不少于 6 的区段有 7 个,分别为:[10][6][10, 5][5, 6][6, 2][10, 5, 6][10, 5, 6, 2]

数据范围

对于 40\% 的数据,满足 1 \le N \le 100

对于 50\% 的数据,满足 1 \le N \le 1000

对于 100\% 的数据,满足 1 \le N \le 10^51 \le A_i, X \le 10^9

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题