Cod sursa(job #125227)

Utilizator h_istvanHevele Istvan h_istvan Data 20 ianuarie 2008 12:10:37
Problema Gardieni Scor 60
Compilator fpc Status done
Runda preONI 2008, Runda 3, Clasa a 10-a Marime 1.75 kb
program gardieni;
type ajanlat = record
               c,a,b:longint;
               kov,elo:word;
               end;
var f:text;
    n,t,i,k,a,min:longint;
    v:array[1..50005] of ajanlat;
    s:extended;

procedure qsort(bal,jobb:longint);
var i,j,va:longint;
    cs:ajanlat;
begin
     i:=bal;
     j:=jobb;
     va:=v[(i+j) div 2].a;
     while(i<=j) do
     begin
          while(v[i].a < va) do inc(i);
          while(v[j].a > va) do dec(j);
          if(i<=j) then
          begin
               cs:=v[i];
               v[i]:=v[j];
               v[j]:=cs;
               inc(i);dec(j);
          end;
     end;
     if(bal<j) then qsort(bal,j);
     if(i<jobb) then qsort(i,jobb);
end;

procedure torol(x:word);
begin
     if (v[x].elo > 0) then v[v[x].elo].kov:=v[x].kov
     else k:=v[x].kov;
     if (v[x].kov > 0) then v[v[x].kov].elo:=v[x].elo;
end;

begin
     assign(f,'gardieni.in');
     reset(f);
     readln(f,n,t);
     for i:=1 to n do
         readln(f,v[i].a,v[i].b,v[i].c);
     close(f);

     qsort(1,n);

     v[1].elo:=0;
     v[1].kov:=2;
     for i:=2 to n-1 do
     begin
          v[i].elo:=i-1;
          v[i].kov:=i+1;
     end;
     v[n].elo:=n-1;
     v[n].kov:=0;

     k:=1;
     s:=0;
     for i:=1 to t do
     begin
          min:=0;
          a:=k;
          while(v[a].a <= i) and (a>0) do
          begin
               if (v[a].b >= i) and ((v[a].c < min) or (min = 0)) then
                  min:=v[a].c;
               if (v[a].b <= i) then torol(a);
               if(v[a].kov > 0) then a:=v[a].kov
               else break;
          end;
          s:=s+min;
     end;

     assign(f,'gardieni.out');
     rewrite(f);
     writeln(f,s:0:0);
     close(f);
end.