#P7868. [COCI2015-2016#2] VUDU

[COCI2015-2016#2] VUDU

题目描述

年轻的 Mirko 最近一直在买 Voodoo 娃娃。因为他对最便宜的东西很感兴趣,所以他每天都在追踪 Voodoo 娃娃的价格。他已经得知了最近 NN 天的娃娃价格,第 ii 天的娃娃价格记为 aia_i

Mirko 认为,连续几天的娃娃平均价格与下一天的娃娃价格之间存在某种联系。他想验证自己的观点,却被一个问题难倒了:“对于一个给定的 PP,在这 NN 天内有多少个不同的连续子序列令娃娃的平均价格大于或等于 PP ?”

两个连续子序列不同当且仅它们的开始位置或结束位置不同。

输入格式

第一行一个整数 NN

接下来一行有 NN 个整数,第 ii 个整数表示 aia_i

最后一行有一个整数 PP

输出格式

一行一个整数,表示在这 NN 天内有多少个不同的连续子序列令娃娃的平均价格大于或等于 PP

3
1 2 3
3
1
3
1 3 2
2
5
3
1 3 2
3
1

提示

【样例 1 解释】

平均数大于等于 3 的子序列只有 3

【样例 2 解释】

平均数大于等于 2 的子序列有 5 个,它们是:

1 3

1 3 2

3

3 2

2

【数据范围】

对于 30%30\% 的数据,1N1041\le N\le 10^4

对于 100%100\% 的数据,1N1061ai1091P1091\le N\le 10^6,1\le a_i\le 10^9,1\le P\le 10^9

【说明】

本题数据点得分依原题,满分 140

题目译自 COCI 2015-2016 CONTEST #2 T5 VUDU