moofest.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 100 行

{
PROG:moofest
LANG:PASCAL
}

program moofest;
const
  range=20000;
  treesize=32767;
  move:array[1..14]of integer=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192);
var
  fin,fout:text;
  v,x:array[1..range]of integer;
  put:array[1..treesize]of boolean;
  count:array[1..treesize]of integer;
  sum:array[1..treesize]of int64;
  s:int64;
  n,i,xmin,xmax,root:integer;
  rootlevel:byte;
procedure qsort(s,t:integer);
  var
    i,j,p,tv,tx:integer;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tv:=v[p];tx:=x[p];
    v[p]:=v[s];x[p]:=x[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (v[j]>=tv) do dec(j);
      if i=j then break;
      v[i]:=v[j];x[i]:=x[j];inc(i);
      while (i<j) and (v[i]<=tv) do inc(i);
      if i=j then break;
      v[j]:=v[i];x[j]:=x[i];dec(j);
    until i=j;
    v[i]:=tv;x[i]:=tx;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
procedure process(a:integer);
  var
    p,level:integer;
  begin
    p:=root;level:=rootlevel;
    while x[a]<>p do begin
      if put[p] then inc(s,v[a]*abs(p-x[a]));
      if x[a]<p then begin
        inc(s,v[a]*(sum[p+move[level]]-x[a]*count[p+move[level]]));
        dec(p,move[level]);dec(level);
      end
      else begin
        inc(s,v[a]*(x[a]*count[p-move[level]]-sum[p-move[level]]));
        inc(p,move[level]);dec(level);
      end;
      inc(count[p]);inc(sum[p],x[a]);
    end;
    put[p]:=true;
    if level>0 then begin
      inc(s,v[a]*(x[a]*count[p-move[level]]-sum[p-move[level]]));
      inc(s,v[a]*(sum[p+move[level]]-x[a]*count[p+move[level]]));
    end;
  end;
begin
  assign(fin,'moofest.in');
  reset(fin);
  readln(fin,n);
  xmin:=range;xmax:=1;
  for i:=1 to n do begin
    readln(fin,v[i],x[i]);
    if x[i]<xmin then xmin:=x[i];
    if x[i]>xmax then xmax:=x[i];
  end;
  close(fin);

  qsort(1,n);

  root:=16384;
  rootlevel:=14;
  while (xmin>root) or (xmax<root) do begin
    if xmin>root then
      inc(root,move[rootlevel])
    else
      dec(root,move[rootlevel]);
    dec(rootlevel);
  end;

  fillchar(put,sizeof(put),0);
  fillchar(count,sizeof(count),0);
  fillchar(sum,sizeof(sum),0);
  s:=0;
  for i:=1 to n do
    process(i);

  assign(fout,'moofest.out');
  rewrite(fout);
  writeln(fout,s);
  close(fout);
end.