比赛 20111108 评测结果 WWWWWWWWWW
题目名称 数对的个数 最终得分 0
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-08 09:23:46
显示代码纯文本
#include <fstream>
#include <cstdlib>

#define I_F "dec.in"
#define O_F "dec.out"

const long MAXn=200000;
const short P=20;

long n,c;
long s[MAXn];
long ans;

void Input();
inline void Swap(long&,long&);
void Qsort(const long, const long);
void Search();
void Output();

int main()
{
	Input();
	Qsort(0,n-1);
	Search();
	Output();
	return 0;
}

void Input()
{
	std::ifstream fin(I_F);
	fin>>n>>c;
	for (long i=0; i<n; fin>>s[i++]);
	fin.close();
}

inline void Swap(long &a, long &b)
{
	long t=a;
	a=b;
	b=t;
}

void Qsort(const long l, const long r)
{
	if (r-l>P)
	{
		long x=s[l+rand()%(r-l+1)];
		long i=l, j=r;
		do
		{
			while (s[i]<x) i++;
			while (s[j]>x) j--;
			if (i<=j)
				Swap(s[i++],s[j--]);
		} while (i<j);
		if (i<r) Qsort(i,r);
		if (l<j) Qsort(l,j);
	}
	else
	{
		bool flag;
		for (long i=l; i<r; i++)
		{
			flag=true;
			for (long j=r; j>i; j--)
				if (s[j]<s[j-1])
					Swap(s[j],s[j-1]),
					flag=false;
			if (flag)
				break;
		}
	}
}

void Search()
{
	long i=0, j=1;
	ans=0;
	for (; j<n; j++)
		for (; (s[j]-s[i]>=c)&&(i<j); i++)
			if (s[j]-s[i]==c)
				ans++;
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<ans<<std::endl;
	fout.close();
}