Cod sursa(job #22008)

Utilizator fogabFodor Gabor fogab Data 25 februarie 2007 13:31:45
Problema Lupul Urias si Rau Scor 32
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.57 kb
type pe=^e;
     e=record
         val,db:longint;
         l,r:pe;
       end;

var f:text;
    d,c:array[1..100000] of longint;
    n,l,x,i,j,grr:longint;
    root,h,h2:pe;
    sol:int64;
    ok:boolean;

function findmax(go:pe):longint;
var a,b:longint;
begin
a:=-1;
b:=-1;
if go^.l<>nil then a:=findmax(go^.l);
if go^.r<>nil then b:=findmax(go^.r);
if b>a then a:=b;
if go^.db<>0 then b:=go^.val;
if b>a then findmax:=b
       else findmax:=a;
end;

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:=c[1];
i:=2;
j:=d[1];
d[n+1]:=-1;
while j<>-1 do
  begin
  while j<>d[i] do begin
    grr:=findmax(root);
    sol:=sol+grr;
    h:=root;
    while h^.val<>grr do
     if grr>h^.val then h:=h^.r
        else h:=h^.l;
    dec(h^.db);
    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.