Range

发布时间: 2018年12月8日 20:11   最后更新: 2018年12月8日 20:13   时间限制: 1000ms   内存限制: 512M

Given $n$ integers $a_1,a_2,\cdots,a_n$ and a const $k$, how many different pairs $(l,r)$ are there meeting the condition that the range of the subsequence $a_l,a_{l+1},\cdots,a_r$ is strictly greater than $k$?

Note: the range of a sequence equals the difference between the maximum and the minimum of the sequence.

The first line of input contains two integers $n,k(1 \le n \le 10^5, 1 \le k \le 10^9)$.

Following that are $n$ integers $a_i(1 \le a_i \le 10^9)$ in the second line.

Display a single integer representing the answer.

复制
5 2
1 2 3 4 5
3

There are three pairs, $(1,4),(1,5),(2,5)$, which meet the condition.

2018 fdupc

2018 FDUPC 程序设计校赛现场赛(网络同步赛)