记录编号	32959	评测结果	AAAAAAAAAT
题目名称	数对的个数	最终得分	90
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	1.005 s
提交时间	2011-11-08 20:49:56	内存使用	2.72 MiB

#include <cstdio>
#include <cstdlib>
using namespace std;

int a[200002]={0};

void swap(int &x,int &y) 
{
    int temp;
    temp=x;
    x=y;
    y=temp;
}

void qqsort(int l,int r)
{
    int ll,rr,temp;
    ll=l;
    rr=r;
    temp=a[rand()%(r-l+1)+l];
    while (ll<=rr)
    {
        while (a[ll]<temp)
            ll++;
        while (temp<a[rr])
            rr--;
        if (ll<=rr)
        {
            swap(a[ll],a[rr]);
            ll++;
            rr--;
        }
    }
    if (l<rr)
        qqsort(l,rr);
    if (ll<r)
        qqsort(ll,r);
}   

int find(int aim,int l,int r,int pos)
{
	int mid,minn,maxn;
	minn=l;
	maxn=r;
	mid=(l+r)/2;
	while (l<r)
	{
		if (a[mid]==aim)
			break;
		else if (a[mid]>aim)
			r=mid-1;
		else// if (a[mid]<aim)
			l=mid+1;
//		if (l<minn)
//		{
//			l=minn;
//			break;
//		}
//		if (r>maxn)
//		{
//			r=maxn;
//			break;
//		}
		mid=(l+r)/2;
	}
	if (a[mid]!=aim)
		return(0);
	else
	{
		l=mid;
		r=mid;
		while (a[l]==aim&&l>=minn)
			l--;
		l++;
		while (a[r]==aim&&r<=maxn)
			r++;
		r--;
		if (l<=pos&&pos<=r)
			return(r-l);
		else
			return(r-l+1);
	}
}

int main(void)
{
	freopen("dec.in","r",stdin);
	freopen("dec.out","w",stdout);
	int i/*,j*/,n,c,temp,total=0;
	scanf("%d %d\n",&n,&c);
	for (i=1;i<=n;i++)
		scanf("%d",&a[i]);
//	a[0]=-2147483647;
	qqsort(1,n);
//	a[n+1]=2147483647;
	for (i=1;i<=n;i++/*=j*/)
	{
//		for (j=i+1;j<=n;j++)
//			if (a[j]!=a[i])
//				break;
		temp=a[i]-c;
		if (temp>a[i])
			total+=find(temp,i+1,n,i);
		else
			total+=find(temp,1,i-1,i);
	}
	printf("%d\n",total);
	fclose(stdin);
	fclose(stdout);
	return(0);
}