BOSS - Ai là sếp
Tác giả: RR
Ngôn ngữ: Pascal
//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
{$M 1000000}
uses math;
const
FINP='';
FOUT='';
MAXN=30111;
snode=65536;
type
list=^node;
node =record
u:longint;
next:list;
end;
nvien=record
ind,sal,height:longint;
boss,count:longint;
end;
ITobj=object
nn,ind:array[1..snode] of longint;
procedure init;
procedure update(u,ii:longint);
function get(u:longint):longint;
end;
var
f1,f2:text;
n,q:longint;
a:array[1..MAXN] of nvien;
xet,ind,c:array[1..MAXN] of longint;
ke:array[1..MAXN] of list;
it:ITobj;
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,q);
for i:=1 to n do
with a[i] do
begin
read(f1,ind,sal,height);
count:=0; boss:=0;
end;
end;
procedure swap(var a,b:longint); inline;
var temp:longint; begin temp:=a; a:=b; b:=temp; end;
procedure swapr(var a,b:nvien); inline;
var temp:nvien; begin temp:=a; a:=b; b:=temp; end;
var mid:longint;
procedure sort1(l,r:longint); inline;
var
i,j:longint;
begin
i:=l; j:=r; mid:=c[l+random(r-l+1)];
repeat
while c[i]<mid do inc(i);
while c[j]>mid do dec(j);
if i<=j then
begin
swap(c[i],c[j]);
swap(ind[i],ind[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort1(i,r);
if l<j then sort1(l,j);
end;
var key,msal,mh,mi:longint;
procedure sort2(l,r:longint);
var
i,j:longint;
begin
key:=l+random(r-l+1); msal:=a[key].sal; mh:=a[key].height;
i:=l; j:=r;
repeat
while (a[i].height<mh) or ((a[i].height=mh) and (a[i].sal<msal)) do inc(i);
while (a[j].height>mh) or ((a[j].height=mh) and (a[j].sal>msal)) do dec(j);
if i<=j then
begin
swapr(a[i],a[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort2(i,r);
if l<j then sort2(l,j);
end;
procedure sort3(l,r:longint);
var
i,j:longint;
begin
mi:=a[l+random(r-l+1)].ind; i:=l; j:=r;
repeat
while a[i].ind<mi do inc(i);
while a[j].ind>mi do dec(j);
if i<=j then
begin
swapr(a[i],a[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort3(i,r);
if l<j then sort3(l,j);
end;
procedure ITobj.init;
var
i:longint;
begin
for i:=1 to snode do
begin
nn[i]:=MAXN;
ind[i]:=0;
end;
end;
procedure ITobj.update(u,ii:longint);
procedure visit(i,l,r:longint);
var
mid:longint;
begin
if (u<l) or (r<u) then exit;
if (l=r) then
begin
nn[i]:=u;
ind[i]:=ii;
exit;
end;
mid:=(l+r)>>1;
visit(i<<1,l,mid);
visit(i<<1+1,mid+1,r);
if nn[i<<1]<nn[i<<1+1] then
begin
nn[i]:=nn[i<<1];
ind[i]:=ind[i<<1];
end
else
begin
nn[i]:=nn[i<<1+1];
ind[i]:=ind[i<<1+1];
end;
end;
begin
visit(1,1,n);
end;
function ITobj.get(u:longint):longint;
var
kq,ikq:longint;
procedure visit(i,l,r:longint);
var
mid:longint;
begin
if (r<u) then exit;
if (u<=l) then
begin
if nn[i]<kq then
begin
kq:=nn[i];
ikq:=ind[i];
end;
exit;
end;
mid:=(l+r)>>1;
visit(i<<1,l,mid);
visit(i<<1+1,mid+1,r);
end;
begin
kq:=MAXN-1; ikq:=0;
visit(1,1,n);
exit(ikq);
end;
procedure add(u:longint; var a:list); inline;
var
p:list;
begin
new(p); p^.u:=u;
p^.next:=a; a:=p;
end;
procedure dfs(u:longint);
var
p:list;
v:longint;
begin
xet[u]:=1;
p:=ke[u];
while p<>nil do
begin
v:=p^.u; p:=p^.next;
if xet[v]=1 then continue;
dfs(v);
a[u].count+=a[v].count+1;
end;
end;
procedure solve;
var
i,u:longint;
begin
//RR hoa luong
for i:=1 to n do c[i]:=a[i].sal;
for i:=1 to n do ind[i]:=i;
sort1(1,n);
for i:=1 to n do a[ind[i]].sal:=i;
//Tim boss
sort2(1,n);
it.init;
for i:=1 to n do ke[i]:=nil;
for i:=n downto 1 do
begin
u:=it.get(a[i].sal);
if u>0 then
begin
a[i].boss:=a[u].ind;
add(i,ke[u]);
end;
it.update(a[i].sal,i);
end;
//Tim so nhan vien
fillchar(xet,sizeof(xet),0);
for i:=n downto 1 do
if xet[i]=0 then dfs(i);
end;
function find(key:longint):longint; inline;
var
l,r,mid,kq:longint;
begin
l:=1; r:=n; kq:=0;
repeat
mid:=(l+r)>>1;
if a[mid].ind>=key then
begin
kq:=mid;
r:=mid-1;
end
else l:=mid+1;
until l>r;
exit(kq);
end;
procedure ans;
var
u,key:longint;
begin
sort3(1,n);
for q:=1 to q do
begin
read(f1,key);
u:=find(key);
writeln(f2,a[u].boss,' ',a[u].count);
end;
end;
var
test:longint;
begin
openF;
read(f1,test);
for test:=1 to test do
begin
inp;
solve;
ans;
end;
closeF;
end.