记录编号	173592	评测结果	AAAAAAAAAAA
题目名称	数对的个数	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.213 s
提交时间	2015-07-29 12:13:06	内存使用	2.59 MiB

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
struct P{
	int a,b;
}shu[200001];
int n,c;
map<int,int>mp;
int flag[200001]={0};
int answer=0;

int work(int k){
	int ans=0;
	int l=1,r=n,pos;
	while (l<=r){
		int mid=(l+r)/2;
		if (shu[k].a-shu[mid].a<c) r=mid;
		else if (shu[k].a-shu[mid].a>c) l=mid+1;
		else {
			pos=mid;
			break;
		}
		if (l==r) return 0;
	}
	r=pos-1;
	ans++;
	while (shu[r].a==shu[pos].a) {
		r--;
		ans++;
	}
	r=pos+1;
	while (shu[r].a==shu[pos].a){
		r++;
		ans++;
	}
	return ans;
}

bool cmp(const P &a,const P &b){
	return a.a<b.a;
}

int main()
{
	freopen("dec.in","r",stdin);
	freopen("dec.out","w",stdout);
	int cnt=0;
	scanf("%d%d",&n,&c);
	for (int i=1;i<=n;++i){
	   scanf("%d",&shu[i].a);
	   if (!mp[shu[i].a]){
			mp[shu[i].a]=++cnt;
			shu[i].b=cnt;
	   }
	   else shu[i].b=mp[shu[i].a];
	}
	sort(shu+1,shu+n+1,cmp);
	for (int i=1;i<=n;++i){
		if (!flag[shu[i].b]){
			int p=work(i);
			flag[shu[i].b]=p;
			answer+=p;
		}
		else answer+=flag[shu[i].b];
	}
	printf("%d",answer);
	return 0;
}