Problem Points on Line

Link: http://codeforces.com/problemset/problem/251/A

A. Points on Line

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Input

The first line contains two integers: n and d (1 ≤ n ≤ 10⁵; 1 ≤ d ≤ 10⁹). The next line contains n integersx₁, x₂, ..., x_n, their absolute value doesn't exceed 10⁹ — the x-coordinates of the points that Petya has got.

It is guaranteed that the coordinates of the points in the input strictly increase.

Output

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 thecin, cout streams or the %I64d specifier.

Sample test(s)

input

4 3
1 2 3 4

output

4

input

4 2
-3 -2 -1 0

output

2

input

5 19
1 10 20 30 50

output

1

Note

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

Thuật toán: Gọi [i,j] là khoảng sao cho abs(x[i] - x[j]) <= d. Gọi số cặp ba điểm trong khoảng [i,j] sao cho điểm x[j] luôn được chọn. Do đó có (i-j)*(i-j-1)/2 cặp.

Code:

/* 
    Coder : Nguyen Duc Tam 
    template for contest
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<cctype>

using namespace std;

/*
    define for statement loop
*/
#define REP(i, start, end, step) for(int i = start; i < end; i += step)
#define DOWN(i, start, end, step) for(int i = start; i > end; i -= step)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

/*
    define operator bit
*/
#define L(x,i) ((x) << (i))
#define R(x,i) ((x) >> (i))
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a) | (b))
#define XOR(a,b) ((a) ^ (b))
#define NOT(a) (~(a))
#define SB(x,i) (OR((x), L(1, (i))))    // x | 1 << i 
#define CB(x,i) (AND((x),NOT(L(1,(i))))) // x & ~(1 << i)
#define TB(x,i) (AND((x), L(1,(i))))    // x & (1 << i) 

/*
    define init data    
*/
#define FILL(a,val) memset(a,val,sizeof(a));
#define INIT(a,l,r,val) REP(i,l,r,1) (a)[i] = val;

/*
    define convert data
*/
#define DIG(c) (int)((c) - '0')
#define CHR(c) (char)((c) + '0')
#define LOW(c) (char)((c) + 32)
#define UPP(c) (char)((c) - 32)

/*
    define math function    
*/
#define sqr(a) (a) * (a)
#define abs(a) (a < 0 ? -(a) : (a))

/*
    define find element in container very fast.
*/
#define LO(c,x) lower_bound(ALL(c),x)   
#define UP(c,x) upper_bound(ALL(c),x)
#define IOF(c,x) distance((c).begin(), LO((c),x))
#define IOL(c,x) distance((c).begin(), UP((c),x))
#define IN(c,x) binary_search(ALL(c),x)
#define ER(c,x) equal_range(ALL(c),x)

/*
    define geo
*/
#define DIS(p,q) sqrt(sqr(p.x - q.x) + sqr(p.y - q.y)) // khoang cach Euclide
#define DIM(p,q) abs(p.x - q.x) + abs(p.y - q.y) // khoang cach mahatan


/*
    define constant
*/

#define EPS 1e-7
#define OO 1000000005
#define N 100005

#define X first
#define Y second

struct Point
{
    double x, y;
    Point(){}
    Point(double x,double y):x(x), y(y){}   
};

struct Node
{
    int value;
    Node* next;
    Node(){}
    Node(int value, Node* next):value(value),next(next){}
};

struct Edge
{
    int src, dst, weight;
    Edge(){}
    Edge(int src, int dst, int weight):src(src), dst(dst), weight(weight){} 
    
};

struct Compare
{
    
    bool operator() (const int i, const int j)
    {
        return i > j;   
    }

    /*
    bool operator() (const Point& p, const Point& q)
    {
        return (p.x != q.x ? p.x < q.x : p.y < q.y);
    }   
    */
    /*
    bool operator()(const Edge& e, const Edge& f)
    {
        return  (e.weight != f.weight ? e.weight > f.weight : e.src != f.src ? 
            e.src < f.src : e.dst < f.dst); // inverse weight
    }
    */
};

    
const int DAY[13] = {-1,31,29,31,30,31,30,31,31,30,31,30,31};

const int dx4[4] = {-1, 0, 1, 0}; //U - R - D - L
const int dy4[4] = {0, 1, 0, -1};

const int dx8[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; //U - UR - R - DR - D - DL - L - UL 
const int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

typedef pair<int,int> II;
typedef pair<II,int> III;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned char UC; 

vector<int>::iterator it, low, up; // using lower_bound, upper_bound
pair<vector<int>::iterator, vector<int>::iterator > bound;  // using function equal_range(first, last, x)
Compare comp;
Point p[2];

int n,d,x[N];
ULL res = 0LL;

int main()
{
    #define Off  false
    if(Off)
    {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    }
    cin >> n >> d;
    REP(i,0,n,1)
        scanf("%d",&x[i]);
    int j = 0;
    REP(i,0,n,1)
    {
        while(x[i] - x[j] > d) j++;
        res += 1LL * (i - j) * (i - j - 1) / 2;
    }
    cout << res << endl;
    return 0;
}