codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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}.