Cod sursa(job #61368)

Utilizator floringh06Florin Ghesu floringh06 Data 19 mai 2007 09:39:42
Problema Triplete Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.97 kb
{$IFDEF NORMAL}
  {$I-,Q-,R-,S-}
{$ENDIF NORMAL}
{$IFDEF DEBUG}
  {$I+,Q+,R+,S-}
{$ENDIF DEBUG}
{$IFDEF RELEASE}
  {$I-,Q-,R-,S-}
{$ENDIF RELEASE}


const maxn=65540;zero=ord('0');
var t:Text;
   count,x,y,o,o2:array[0..maxn]of longint;
   n,m,i,lg,j,sol:longint;s:string;
   Procedure radixSort(var by,a,b:array of longint);
   var i:longint;
   begin
      fillchar(count,sizeof(count),0);
      for i:=1 to M do inc(count[by[i]]);
      for i:=1 to N+1 do inc(count[i],count[i-1]);
      for i:=M downto 1 do
      begin A[count[by[B[i]]]]:=B[i];dec(count[by[b[i]]]);end;
   end;
   function merge(p1,p2:longint):longint;
   var juma,return,lo1,hi1,lo2,hi2,lo,hi:longint;
   begin
      return:=0;
      lo:=count[p1]+1;hi:=count[p1+1];
      lo1:=count[p1+1]+1;hi1:=count[p1+1];
      while lo<=hi do
      begin
         juma:=(lo+hi)div 2;
         if Y[juma]>p2 then
         begin if lo1>juma then lo1:=juma;hi:=juma-1;end else lo:=juma+1;
      end;
      lo2:=count[p2]+1;hi2:=count[p2+1];
      while (lo1<=hi1)and(lo2<=hi2)do
      begin
         if Y[lo1]=Y[lo2]then begin inc(return);inc(lo1);inc(lo2);end else
         if Y[lo1]<Y[lo2] then inc(lo1) else inc(lo2);
      end;
      merge:=return;
   end;
begin
   sol:=0;
   fillchar(x,sizeof(x),0);
   fillchar(y,sizeof(y),0);
   assign(t,'triplete.in');reset(T);readln(t,n,m);
   for i:=1 to m do
   begin
      readln(t,s);lg:=length(s);j:=1;O[i]:=i;
      while s[j]<>' ' do begin x[i]:=x[i]*10+ord(s[j])-zero;inc(j);end;
      while S[j]=' 'do inc(j);
      while j<=lg do begin y[i]:=y[i]*10+ord(s[j])-zero;inc(j);end;
      if X[i]>y[i]then begin x[0]:=x[i];x[i]:=y[i];Y[i]:=x[0];end;
   end;close(T);Radixsort(Y,O2,O);radixSort(X,O,O2);
   for i:=1 to M do O2[i]:=X[O[i]];for i:=1 to M do X[i]:=o2[i];
   for i:=1 to M do O2[i]:=y[O[i]];for i:=1 to M do y[i]:=o2[i];
   for i:=1 to M do sol:=sol+merge(X[i],Y[i]);
   assign(t,'triplete.out');rewrite(T);writeln(T,sol);close(T);
end.