Cod sursa(job #137776)

Utilizator CezarMocanCezar Mocan CezarMocan Data 17 februarie 2008 14:42:44
Problema Heavy metal Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.74 kb
type roaker=record
                x,y:longint;
                end;

var n,i,j,poz,p1,p2:longint;
    aux:roaker;
    v:array[0..100010] of roaker;
    x,y:array[0..100100] of longint;

procedure qsort(ls,ld:longint);
var i,j:longint;
begin
  i:=ls;j:=ld;
  while true do begin
    while (v[i].y<=v[j].y)and(i<>j) do inc(i);
    if i=j then break;
    aux:=v[i];v[i]:=v[j];v[j]:=aux;dec(j);
    while (v[i].y<=v[j].y)and(i<>j) do dec(j);
    if i=j then break;
    aux:=v[i];v[i]:=v[j];v[j]:=aux;inc(i);
  end;
  if j-1>ls then qsort(ls,j-1);
  if j+1<ld then qsort(j+1,ld);
end;

function cauta(l,r:longint):longint;
var m:longint;
begin
m:=(l+r) div 2;
if (v[m].y<=v[i].x)and((v[m+1].y>v[i].x)or(m+1=i)) then
        begin
        cauta:=m;
        exit;
        end;
if l>=r then
        begin
        cauta:=0;
        exit;
        end;
if v[m].y<=v[i].x then
        cauta:=cauta(m+1,r);
if v[m].y>v[i].x then
        cauta:=cauta(l,m-1);
end;

function max(a,b:longint):longint;
begin
if a>b then
        max:=a
else
        max:=b;
end;


begin
assign(input,'heavymetal.in');reset(input);
assign(output,'heavymetal.out');rewrite(output);
readln(n);
for i:=1 to n do
        readln(v[i].x,v[i].y);
randomize;
for i:=1 to n div 2 do
        begin
        p1:=random(n)+1;
        p2:=random(n)+1;
        aux:=v[p1];v[p1]:=v[p2];v[p2]:=aux;
        end;
qsort(1,n);
//x[i]=daca l-am luat pe i
x[1]:=v[1].y-v[1].x;
for i:=2 to n do
        begin
        if v[i].x<v[1].x then
                poz:=0
        else
                poz:=cauta(1,i-1);
        x[i]:=max(x[poz],y[poz])+v[i].y-v[i].x;
        y[i]:=max(x[i-1],y[i-1]);
        end;
writeln(max(x[n],y[n]));
close(input);close(output);
end.