251A.md (1576B)
1 Source: https://codeforces.com/problemset/problem/251/A 2 3 A. Points on Line 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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*. 22 23 Note that the order of the points inside the group of three chosen points doesn't matter. 24 25 Input 26 27 The first line contains two integers: *n* and *d* (1 ≤ *n* ≤ 105; 1 ≤ *d* ≤ 109). The next line contains *n* integers *x*1, *x*2, ..., *x**n*, their absolute value doesn't exceed 109 — the *x*-coordinates of the points that Petya has got. 28 29 It is guaranteed that the coordinates of the points in the input strictly increase. 30 31 Output 32 33 Print a single integer — the number of groups of three points, where the distance between two farthest points doesn't exceed *d*. 34 35 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. 36 37 Examples 38 39 Input 40 41 ``` 42 4 3 43 1 2 3 4 44 ``` 45 46 Output 47 48 ``` 49 4 50 ``` 51 52 Input 53 54 ``` 55 4 2 56 -3 -2 -1 0 57 ``` 58 59 Output 60 61 ``` 62 2 63 ``` 64 65 Input 66 67 ``` 68 5 19 69 1 10 20 30 50 70 ``` 71 72 Output 73 74 ``` 75 1 76 ``` 77 78 Note 79 80 In the first sample any group of three points meets our conditions. 81 82 In the seconds sample only 2 groups of three points meet our conditions: {-3, -2, -1} and {-2, -1, 0}. 83 84 In the third sample only one group does: {1, 10, 20}.