Points on Line

题意翻译

## 题目描述 Petya很喜欢点。最近，他的妈妈给了他n个位于OX（实数轴）上的点。现在，Petya想知道有多少种不同的方法可以在数轴上选择3个不同点，使3个点中距离最远的两个点的距离不超过d。 注意：三个点的排列顺序是无关紧要的（意思就是说，三个点是相同的，交换顺序也只算1种）。 ## 输入输出格式 ###### 输入格式： 第一行有两个数：n（1<=n<=1e5）d（1<=d<=1e9）。下面一行包含n个整数x1,x2,x3,x4...,xn（绝对值小于等于1e9），表示妈妈给Petya的点的坐标。 保证坐标按绝对升序输入。 ###### 输出格式： 输出一个整数————选出三个数，使最远的两个数之间的距离不超过d，的方法数。 在C++中，请不要用 %lld 来读入64位的整数。推荐使用 cin 和 cout 或 %l64d 来读入。 ## 输入输出样例 （emmm，不会用格式，不写进来了） ## 说明 在样例一中，任何挑选方式都是可行的。 在样例二中只有{-3, -2, -1}和{-2, -1, 0}是可行的。 在第三个样例中只有{1, 10, 20}是可行的。 感谢@Spoiler_haiwenhan 提供的翻译

题目描述

Little Petya likes points a lot. Recently his mom has presented him $ n $ points lying on the line $ OX $ . Now Petya is wondering in how many ways he can choose three distinct points so that the distance between the two farthest of them doesn't exceed $ d $ . Note that the order of the points inside the group of three chosen points doesn't matter.

输入输出格式

输入格式

The first line contains two integers: $ n $ and $ d $ ( $ 1<=n<=10^{5}; 1<=d<=10^{9} $ ). The next line contains $ n $ integers $ x_{1},x_{2},...,x_{n} $ , their absolute value doesn't exceed $ 10^{9} $ — the $ x $ -coordinates of the points that Petya has got. It is guaranteed that the coordinates of the points in the input strictly increase.

输出格式

Print a single integer — the number of groups of three points, where the distance between two farthest points doesn't exceed $ d $ . Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

4 3
1 2 3 4

输出样例 #1

4

输入样例 #2

4 2
-3 -2 -1 0

输出样例 #2

2

输入样例 #3

5 19
1 10 20 30 50

输出样例 #3

1

说明

In the first sample any group of three points meets our conditions. In the seconds sample only 2 groups of three points meet our conditions: {-3, -2, -1} and {-2, -1, 0}. In the third sample only one group does: {1, 10, 20}.