Cod sursa(job #24906)

Utilizator fogabFodor Gabor fogab Data 3 martie 2007 23:26:07
Problema Lupul Urias si Rau Scor 72
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.6 kb
type pe=^e;
     e=record
         val,db:int64;
         l,r:pe;
       end;
var f:text;
    d,c:array[1..100005] of int64;
    n,l,x,i,j:longint;
    root,h,h2:pe;
    sol:int64;
    ok:boolean;


procedure quicksort(l,r:dword);
var i,j,x,y:dword;
begin
 i:=l;j:=r;x:=d[(l+r) div 2];
 repeat
   while d[i]>x do i:=i+1;
   while x>d[j] do j:=j-1;
   if i<=j then begin
                y:=d[i];
                d[i]:=d[j];
                d[j]:=y;
                y:=c[i];
                c[i]:=c[j];
                c[j]:=y;
                i:=i+1;
                j:=j-1;
                end;
 until i>j;
 if l<j then quicksort(l,j);
 if i<r then quicksort(i,r);
end;

begin
assign(f,'lupu.in');
reset(f);
readln(f,n,x,l);
for i:=1 to n do
  begin
  readln(f,d[i],c[i]);
  d[i]:=(x-d[i]) div l;
  end;
close(f);
quicksort(1,n);
new(root);
root^.l:=nil;
root^.r:=nil;
root^.db:=1;
root^.val:=-1;
i:=1;
j:=d[1];
d[n+1]:=-1;
sol:=0;
while j<>-1 do
  begin
  while j<>d[i] do begin
    h:=nil;
    h2:=root;
    while h2^.r<>nil do
      begin
      h:=h2;
      h2:=h2^.r;
      end;
    sol:=sol+h2^.val;
    if h2^.db<>1 then dec(h2^.db)
       else if (h2^.l=nil) then begin
                                h^.r:=nil;
                                dispose(h2);
                                end
            else begin
                 h^.r:=h2^.l;
                 dispose(h2);
                 end;
    dec(j);
    end;
  h:=root;
  ok:=true;
  while ok do
        if c[i]=h^.val then begin
                            inc(h^.db);
                            ok:=false;
                            end
           else if c[i]<h^.val then
              if h^.l=nil then begin
                               new(h2);
                               h2^.l:=nil;
                               h2^.r:=nil;
                               h2^.val:=c[i];
                               h2^.db:=1;
                               h^.l:=h2;
                               ok:=false;
                               end
                 else h:=h^.l
           else
              if h^.r=nil then begin
                               new(h2);
                               h2^.l:=nil;
                               h2^.r:=nil;
                               h2^.val:=c[i];
                               h2^.db:=1;
                               h^.r:=h2;
                               ok:=false;
                               end
                 else h:=h^.r;
      inc(i);
  end;
assign(f,'lupu.out');
rewrite(f);
writeln(f,sol);
close(f);
end.