MCONVOI - Con Voi
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$MODE OBJFPC}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 300111;
base = 1000000007;
var
f1,f2 : text;
n,d : longint;
x,y,f,reg : array[0..MAXN] of longint;
last,sl,ind : array[1..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
read(f1,n);
for i:=1 to n do
read(f1,x[i],y[i]);
end;
procedure swap(var a,b:longint); inline;
var
tmp:longint;
begin
tmp:=a; a:=b; b:=tmp;
end;
procedure sort(l,r:longint); inline;
var
i,j,mx,my,key:longint;
begin
i:=l; j:=r; key:=l+random(r-l+1);
mx:=x[key]; my:=y[key];
repeat
while (y[i]<my) or ((y[i]=my) and (x[i]>mx)) do inc(i);
while (y[j]>my) or ((y[j]=my) and (x[j]<mx)) do dec(j);
if i<=j then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function find(key:longint):longint; inline;
var
res,l,r,mid:longint;
begin
res:=0; l:=1; r:=d;
while (l<=r) do
begin
mid:=(l+r)>>1;
if last[mid]<key then
begin
res:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
exit(res);
end;
function find1(l,r,key:longint):longint; inline;
var
mid,res:longint;
begin
res:=r;
while (l<=r) do
begin
mid:=(l+r)>>1;
if last[mid]<key then
begin
res:=mid;
r:=mid-1;
end
else l:=mid+1;
end;
exit(res);
end;
function find2(l,r,key:longint):longint; inline;
var
mid,res:longint;
begin
res:=l;
while (l<=r) do
begin
mid:=(l+r)>>1;
if ind[mid]<key then
begin
res:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
exit(res);
end;
procedure solve;
var
i,k,u,v:longint;
begin
//Tinh do dai day con tang dai nhat
d:=0;
for i:=1 to n do
begin
k:=find(x[i]);
f[i]:=k+1;
d:=max(d,k+1);
last[k+1]:=x[i];
inc(sl[k+1]);
end;
writeln(f2,d);
//Dem phan phoi
for i:=2 to d do
sl[i]:=sl[i-1]+sl[i];
for i:=n downto 1 do
begin
last[sl[f[i]]]:=x[i];
ind[sl[f[i]]]:=i;
reg[sl[f[i]]]:=f[i];
dec(sl[f[i]]);
end;
//Dem so luong
fillchar(f,sizeof(f),0);
f[1]:=1;
for i:=2 to n do
if reg[i]=1 then f[i]:=f[i-1]+1
else
begin
u:=find1(sl[reg[i]-1]+1,sl[reg[i]],last[i]);
v:=find2(sl[reg[i]-1]+1,sl[reg[i]],ind[i]);
if reg[u-1]+2=reg[i] then f[u-1]:=0;
if u>v then f[i]:=1
else f[i]:=f[v]-f[u-1]; if f[i]<0 then inc(f[i],base);
if (i<>sl[reg[i]]+1) then
begin
f[i]:=(f[i-1]+f[i]);
if f[i]>base then dec(f[i],base);
end;
end;
writeln(f2,f[n]);
end;
begin
openF;
inp;
sort(1,n);
solve;
closeF;
end.