Cod sursa(job #137267)

Utilizator marius21Petcu Marius marius21 Data 17 februarie 2008 10:42:49
Problema Heavy metal Scor 0
Compilator fpc Status done
Runda preONI 2008, Runda 4, Clasele 5-8 Marime 1.37 kb
type band=record
   cncl:boolean;
   a,b:longint;
   end;
var a,tmp: array[1..100001] of band;
f,g:text;
s,i,n:longint;

function max(p1,p2:longint):longint;
begin
if p1>p2 then max:=p1 else max:=p2;
end;

procedure sort(si,sj:longint);
var mid,i,j,t:longint;
begin
if si<sj then begin
   mid:=(si+sj)div 2;
   sort(si,mid);
   sort(mid+1,sj);
   i:=si;
   j:=mid+1;
   t:=si;
   while (i<=mid) and (j<=sj) do
      if a[i].a<=a[j].a then  begin
         tmp[t]:=a[i];
         inc(t);
         inc(i);
         end else
         begin
         tmp[t]:=a[j];
         inc(t);
         inc(j);
         end;
   while i<=mid do begin
         tmp[t]:=a[i];
         inc(t);
         inc(i);
         end;
   while j<=sj do begin
         tmp[t]:=a[j];
         inc(t);
         inc(j);
         end;
   for i:=si to sj do
      a[i]:=tmp[i];
   end;
end;

begin
assign(f,'heavymetal.in');
assign(g,'heavymetal.out');
reset(f);
rewrite(g);
read(f,n);
for i:=1 to n do
   read(f,a[i].a,a[i].b);
sort(1,n);
s:=a[1].b-a[1].a;
a[n+1].a:=maxlongint;
a[n+1].b:=maxlongint;
for i:=2 to n+1 do
   if a[i-1].b>=a[i].a then begin
      a[i].a:=a[i-1].a;
      a[i].b:=max(a[i].b,a[i-1].b);
      a[i-1].cncl:=true;
      s:=s-(a[i-1].b-a[i-1].a)+(a[i].b-a[i].a);
      end else
      s:=s+(a[i].b-a[i].a);
writeln(g,s);
close(f);
close(g);
end.