比赛 |
20111108 |
评测结果 |
AAAAAAAAAA |
题目名称 |
数对的个数 |
最终得分 |
100 |
用户昵称 |
Czb。 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-11-08 10:02:15 |
显示代码纯文本
#include<fstream>
#include<stdlib.h>
using namespace std;
ifstream cin("dec.in");
ofstream cout("dec.out");
struct aaa
{
long long a,s;
}f[200001];
int n,m;
long long a[200001],k,t1,t2,ans;
int cmp(const void *a,const void *b)
{
return *(long long *)a-*(long long *)b;
}
void solve(int l,int r)
{
int h=(l+r)/2;
if(f[h].a==t1)
{
ans+=t2*f[h].s;
return;
}
if(l>=r)
return;
if(f[h].a>t1)
{
solve(l,h-1);
}
else
{
solve(h+1,r);
}
}
int main()
{
int i,j;
cin>>n>>k;
for(i=1;i<=n;i++)
cin>>a[i];
qsort(a+1,n,8,cmp);
for(i=1;i<=n;i++)
{
if(a[i]!=a[i-1])
{
m++;
f[m].a=a[i];
f[m].s++;
}
else
{
f[m].s++;
}
}
for(i=1;i<=m;i++)
{
t1=f[i].a-k;
t2=f[i].s;
solve(1,m);
}
if(k==0)
{
ans=(ans-n)>>1;
}
cout<<ans<<endl;
return 0;
}