Cod sursa(job #7721)

Utilizator bigsarpeadrian bigsarpe Data 22 ianuarie 2007 09:20:17
Problema Triplete Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.43 kb
const maxn=4100;maxmuc=65600;
var t:Text;
    V,X,Y:array[0..maxmuc]of longint;{integer}
    Grad:Array[0..maxn]of longint;
    sol,lo1,lo2,hi1,hi2,n,m,i,j,loc:longint;
    Procedure Mergesort(lo,hi:longint;var a,b:array of longint);
    var i,j,lg,juma:longint;
    begin
       if lo<hi then
       begin
          juma:=(lo+hi)div 2;for i:=lo to hi do B[i]:=A[i];
          mergesort(lo,juma,b,a);mergesort(juma+1,hi,b,a);
          i:=lo;j:=juma+1;
          for lg:=lo to hi do if(j>hi)or(i<=juma)and(B[i]<=B[j]) then
          begin A[lg]:=B[i];inc(i);end else begin A[lg]:=B[j];inc(j);end;
       end;
    end;
begin
   assign(t,'triplete.in');reset(t);readln(t,n,m);
   for i:=1 to M do
   begin
      readln(T,X[i],Y[i]);
      if X[i]>Y[i] then begin X[0]:=X[i];X[i]:=Y[i];Y[i]:=X[0];end;
      inc(grad[X[i]]);
   end;close(T);
   for i:=1 to N+1 do inc(Grad[i],grad[i-1]);
   for i:=1 to M do begin loc:=Grad[X[i]];V[loc]:=Y[i];dec(GRad[X[i]]);end;
   for i:=1 to N do Mergesort(Grad[i]+1,grad[i+1],V,X);
   for i:=1 to N do for j:=i+1 to N do
   begin
      lo1:=Grad[i]+1;hi1:=grad[i+1];lo2:=grad[j]+1;hi2:=grad[j+1];
      while (lo1<=hi1)and(lo2<=hi2) do
      begin
         if V[lo1]<V[lo2] then inc(lo1) else
         if V[lo1]=V[lo2] then begin inc(lo1);inc(lo2);inc(Sol);end else
         if V[lo1]>V[lo2] then inc(lo2);
      end;
   end;
   assign(t,'triplete.out');rewrite(T);writeln(T,sol);close(T);
end.