PBCSEQ - Các đoạn nguyên

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=100001;
var n,num:longint;
    a,b,f:array[1..maxn] of longint;

procedure rf;
var i:longint;
begin
     assign(input,fi); reset(input);
     read(n);
     for i:=1 to n do read(a[i],b[i]);
     close(input);
end;

procedure sort(l,r:longint);
var i,j,x,y,k,t:longint;
begin
     i:=l; j:=r;
     k:=(l+r) shr 1;
     x:=a[k]; y:=b[k];
     repeat
           while (a[i]<x) or ((a[i]=x) and (b[i]>y)) do i:=i+1;
           while (a[j]>x) or ((a[j]=x) and (b[j]<y)) do j:=j-1;
           if i<=j then
           begin
                t:=a[i]; a[i]:=a[j]; a[j]:=t;
                t:=b[i]; b[i]:=b[j]; b[j]:=t;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function bs(y:longint):longint;
var l,r,m,i:longint;
begin
     l:=1; r:=num;
     while l<=r do
     begin
          m:=(l+r) shr 1;
          if b[f[m]]<=y then l:=m+1
          else r:=m-1;
     end;
     for i:=m-2 to m+2 do
         if (i>0) and (i<=num) and (b[f[i]]>y) then break;
     bs:=i;
end;

procedure pr;
var i,t:longint;
begin
     sort(1,n);
     num:=1; f[1]:=n;
     for i:=n-1 downto 1 do
     begin
          if b[i]>=b[f[num]] then
          begin
               inc(num);
               f[num]:=i;
          end
          else
          begin
               t:=bs(b[i]);
               f[t]:=i;
          end;
     end;
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     writeln(num);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download