PBCSEQ - Các đoạn nguyên
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program PBCSEQ;
Const
input = '';
output = '';
maxn = 100000;
Var
a,b,L,Start: array[0..maxn + 1] of integer;
n,m: integer;
Procedure init;
Var
f: text;
i: integer;
Begin
Assign(f, input);
Reset(f);
Readln(f, n);
For i:= 1 to n do read(f, a[i], b[i]);
Close(f);
End;
Procedure swap(var x,y: integer);
Var
t: integer;
Begin
t:= x;
x:= y;
y:= t;
End;
Procedure quicksort;
Procedure partition(low,high: integer);
Var
i,j,p,p1,p2: integer;
Begin
If low >= high then exit;
i:= low;
j:= high;
p:= random(high - low + 1) + low;
p1:= a[p];
p2:= b[p];
Repeat
While (b[i] > p2) or ((b[i] = p2) and (a[i] < p1)) do inc(i);
While (b[j] < p2) or ((b[j] = p2) and (a[j] > p1)) do dec(j);
If i <= j then
Begin
if i < j then
Begin
swap(a[i],a[j]);
swap(b[i],b[j]);
End;
inc(i);
dec(j);
End;
Until i > j;
partition(low,j);
partition(i,high);
End;
Begin
partition(1,n);
End;
Procedure enter;
Begin
a[0]:= low(integer);
a[n + 1]:= high(integer);
m:= 1;
L[n + 1]:= 1;
Start[1]:= n + 1;
End;
Function Find(i: integer): integer;
Var
inf,sup,med,j: integer;
Begin
inf:= 1;
sup:= m + 1;
Repeat
med:= (inf + sup) div 2;
j:= Start[med];
If a[j] >= a[i] then inf:= med else sup:= med;
Until inf + 1 = sup;
Find:= Start[inf];
End;
Procedure optimize;
Var
i,j,k: integer;
Begin
For i:= n downto 0 do
Begin
j:= Find(i);
k:= L[j] + 1;
If k > m then
Begin
m:= k;
Start[k]:= i;
End
else
if a[Start[k]] <= a[i] then Start[k]:= i;
L[i]:= k;
End;
End;
Procedure printresult;
Var
f: text;
i: integer;
Begin
Assign(f, output);
Rewrite(f);
Writeln(f, m - 2);
Close(f);
End;
Begin
init;
quicksort;
enter;
optimize;
printresult;
End.