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.