比赛 20111108 评测结果 AAAAEEAAAE
题目名称 数对的个数 最终得分 70
用户昵称 Des. 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-11-08 10:20:14
显示代码纯文本
var a,b,c:array[0..200000]of longint;
    t,k,m,n,i,j,ans:longint;
procedure qsort(l,r:longint);
var t,k,i,j,m:longint;
begin
m:=a[(l+r)div 2];
i:=l;
j:=r;
repeat
  while a[i]<m do inc(i);
  while a[j]>m do dec(j);
  if i<=j then
    begin
      k:=a[i];
      a[i]:=a[j];
      a[j]:=k;
      inc(i);
      dec(j);
    end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function sou(l,r,o:longint):longint;
var t,k,i,j:longint;
begin
if l+1=r then
  begin
    if b[r]=o then exit(r);
    if b[l]=o then exit(l);
    if (o>b[l])and(o<b[r]) then exit(0);
  end;
if l=r then
  begin
    if b[l]=o then exit(l);
    if b[l]<>o then exit(0);
  end;
k:=(l+r)div 2;
if b[k]<=o then exit(sou(k,r,o))
else exit(sou(l,k-1,o));
end;


begin
assign(input,'dec.in');
reset(input);
assign(output,'dec.out');
rewrite(output);
readln(n,m);
for t:=1 to n do
  read(a[t]);
qsort(1,n);
i:=-maxlongint;
j:=0;
for t:=1 to n do
  begin
    if a[t]<>i then
      begin
        inc(j);
        inc(c[j]);
        b[j]:=a[t];
        i:=a[t];
      end
    else
      begin
        inc(c[j]);
      end;
  end;
b[0]:=j;
ans:=0;
for i:=1 to b[0] do
  begin
    if b[i]+m>b[b[0]] then break;
    j:=sou(i,b[0],b[i]+m);
    if j>0 then
      if m>0 then
        ans:=ans+c[i]*c[j]
      else ans:=ans+c[i]*(c[j]-1);
  end;
writeln(ans);
close(output);
end.