A145357.星尘观测窗

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

SherrySherry 正在记录一条星尘轨道上的能量变化。轨道上有 nn 个观测点,第 ii 个观测点的能量值为 aia_i

她想选择一段连续的观测区间 [l,r][l,r]。如果这段区间内最大能量值和最小能量值的差不超过 DD,那么这段区间就被称为“稳定观测窗”。

请你计算一共有多少个稳定观测窗。

这里的稳定观测窗指的是一个连续区间。只要两个区间的左端点或右端点不同,就认为它们是不同的稳定观测窗。

也就是说,即使一个稳定观测窗可以继续向左或向右延长,并且延长后仍然稳定,原来的区间和延长后的区间也会分别计算。

需要统计满足下面条件的连续区间数量:

max(al,al+1,,ar)min(al,al+1,,ar)D\max(a_l,a_{l+1},\cdots,a_r)-\min(a_l,a_{l+1},\cdots,a_r)\le D

输入格式

第一行输入两个整数 n,Dn,D,分别表示观测点数量和稳定差值上限。

第二行输入 nn 个整数 a1,a2,,ana_1,a_2,\cdots,a_n,表示每个观测点的能量值。

输出格式

输出一个整数,表示稳定观测窗的数量。

输入输出样例

  • 输入#1

    6 3
    1 3 2 6 4 5

    输出#1

    12
  • 输入#2

    5 0
    2 2 1 1 1

    输出#2

    9

说明/提示

数据范围

1n2×1051\le n\le 2\times 10^5

0D1090\le D\le 10^9

1ai1091\le a_i\le 10^9

答案可能较大,请使用 long long

输入解题思路,AI测评打分。不知道怎么写?

首页