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

Tác giả: ladpro98

Ngôn ngữ: Pascal

program pbcseqBIT;
uses    math;
const   maxN=100001;
        maxV=1000000;
        fi='';
type    range=record
        l,r:longint;
        end;
var     f:array[0..maxN] of longint;
        bit:array[0..maxV] of longint;
        a:array[0..maxN] of range;
        n:longint;
procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
                readln(inp,a[i].l,a[i].r);
        close(inp);
end;

procedure update(i,v:longint);

begin
        while i<=maxV do
        begin
                bit[i]:=max(bit[i],v);
                i:=i+i and (-i);
        end;
end;

function get(i:longint):longint;
var     t:longint;
begin
        t:=0;
        while i>0 do
        begin
                t:=max(t,bit[i]);
                i:=i-i and (-i);
        end;
        exit(t);
end;

function smaller(a,b:range):boolean;
begin
        if a.l<b.l then exit(true);
        if a.l>b.l then exit(false);
        if a.r>b.r then exit(true);
        exit(false);
end;

function bigger(a,b:range):boolean;
begin
        if a.l>b.l then exit(true);
        if a.l<b.l then exit(false);
        if a.r<b.r then exit(true);
        exit(false);
end;

procedure swap(i,j:longint);
var     t:range;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     i,j:longint;
        p:range;

begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while smaller(a[i],p) do inc(i);
                while bigger(a[j],p) do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);
                        dec(j);
                end;
        until i>j;
        sort(l,j);
        sort(i,r);
end;

procedure dp;
var     i:longint;

begin
        a[0].r:=maxV;
        a[n+1].r:=1;
        //update(0,1);
        //for i:=1 to maxV do bit[i]:=1;
        for i:=n+1 downto 0 do
        begin
                f[i]:=get(a[i].r)+1;
                update(a[i].r,f[i]);
        end;

end;

procedure output;
begin
        write(f[0]-2);
end;

begin
        input;
        sort(1,n);
        dp;
        output;
end.

Download