Cod sursa(job #764792)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 6 iulie 2012 12:19:51
Problema Gutui Scor 90
Compilator fpc Status done
Runda teme_upb Marime 2.21 kb
Program lupu;
type tip=record
      tm,v:int64;
       end;
 var h:array [0..100005] of int64;
     t:array [0..100005] of tip;
     b1:array [1..1 shl 17] of integer;
     i,n,hp,lev:longint;
     rez:int64;
     x,l,max,d,g:int64;
     fi,fo:text;
procedure swap(var a,b:int64);
 var aux:int64;
begin
 aux:=a; a:=b; b:=aux;
end;
procedure coboara(nod:longint);
begin
 if (h[2*nod]>h[nod]) and (h[2*nod]>h[2*nod+1]) then begin
                                 swap(h[nod],h[2*nod]);
                                if 2*nod<hp then coboara(2*nod);
                                                    end
 else if (h[2*nod+1]>h[nod]) and (h[2*nod+1]>=h[2*nod]) then begin
                               swap(h[nod],h[2*nod+1]);
                               if 2*nod+1<hp then coboara(2*nod+1);
                                                     end;
end;
procedure urca(nod:longint);
 var aux:longint;
begin
 if (nod>1) and (h[nod div 2]<h[nod]) then begin
                      swap(h[nod],h[nod div 2]);
                      urca(nod div 2);
                       end;
end;
procedure sterge;
begin
 h[1]:=h[hp]; h[hp]:=-1; dec(hp); coboara(1);
end;
procedure insert(val:longint);
begin
 inc(hp); h[hp]:=val; urca(hp);
end;
procedure sort(l,r:longint);
 var k,i,j:longint; y:tip;
 begin
  i:=l; j:=r;
   k:=t[(l+r) div 2].tm;
 repeat
  while t[i].tm>k do inc(I);
   while t[j].tm<k do dec(j);
 if i<=j then begin
               y:=t[i]; t[i]:=t[j]; t[j]:=y;
                inc(i); dec(j);
              end;
 until i>=j;
  if l<j then sort(l,j);
   if i<r then sort(i,r);
end;
begin
 assign(fi,'gutui.in');
  assign(fo,'gutui.out');
 settextbuf(fi,b1);
 reset(fi); rewrite(fo); readln(fi,n,x,l);
  for i:=1 to n do begin
                    readln(fi,d,g); h[i]:=-1;
                    t[i].tm:=(x-d) div l;
                    t[i].v:=g;
                    if t[i].tm>max then max:=t[i].tm;
                   end;
  lev:=1; sort(1,n); h[0]:=-1;
  for i:=max downto 0 do begin
       while (t[lev].tm=i) and (lev<=n) do begin insert(t[lev].v); inc(lev); end;
          if hp>0 then begin rez:=rez+h[1]; sterge; end;
                       end;
  write(fo,rez);
 close(fo);
end.