BOSS - Ai là sếp
Tác giả: ll931110
Ngôn ngữ: Pascal
program BOSS;
const
input = '';
output = '';
maxn = 30000;
maxv = 1000000;
type
pnode = ^tnode;
tnode = record
val: longint;
link: pnode;
end;
var
id,h,s,tmp,tmppos: array[1..maxn] of longint;
tx,pre,nchi: array[1..maxn] of longint;
idpos: array[1..maxv] of longint;
a: array[1..maxn] of pnode;
free: array[1..maxn] of boolean;
i,nTest: longint;
n,q: longint;
fi,fo: text;
procedure openfile;
begin
assign(fi, input);
reset(fi);
assign(fo, output);
rewrite(fo);
end;
procedure closefile;
begin
close(fo);
close(fi);
end;
procedure init;
var
i: longint;
begin
readln(fi, n, q);
for i := 1 to n do readln(fi, id[i], s[i], h[i]);
end;
procedure sw(var x,y: longint);
var
z: longint;
begin
z := x; x := y; y := z;
end;
procedure swap1(i,j: longint);
begin
sw(id[i],id[j]); sw(h[i],h[j]); sw(s[i],s[j]);
end;
procedure sort1(lo,hi: longint);
var
i,j,p: longint;
begin
if lo >= hi then exit;
i := lo; j := hi; p := s[random(hi - lo + 1) + lo];
repeat
while s[i] < p do inc(i);
while s[j] > p do dec(j);
if i <= j then
begin
if i < j then swap1(i,j);
inc(i);
dec(j);
end;
until i > j;
sort1(lo,j); sort1(i,hi);
end;
procedure swap2(i,j: longint);
begin
sw(tmp[i],tmp[j]); sw(tmppos[i],tmppos[j]);
end;
procedure sort2(lo,hi: longint);
var
i,j,p: longint;
begin
if lo >= hi then exit;
i := lo; j := hi; p := tmp[random(hi - lo + 1) + lo];
repeat
while tmp[i] < p do inc(i);
while tmp[j] > p do dec(j);
if i <= j then
begin
if i < j then swap2(i,j);
inc(i);
dec(j);
end;
until i > j;
sort2(lo,j); sort2(i,hi);
end;
//BIT operations
procedure update(x,val: longint);
begin
while x > 0 do
begin
if tx[x] > val then tx[x] := val;
x := x - (x and -x);
end;
end;
function calc(x: longint): longint;
var
r: longint;
begin
r := maxv;
while x <= maxn do
begin
if r > tx[x] then r := tx[x];
x := x + (x and -x);
end;
calc := r;
end;
procedure add(x,y: longint);
var
p: pnode;
begin
new(p);
p^.val := y;
p^.link := a[x];
a[x] := p;
end;
procedure DFS(u: longint);
var
p: pnode;
begin
free[u] := false;
p := a[u];
while p <> nil do
begin
if p^.val <> pre[u] then
begin
if free[p^.val] then DFS(p^.val);
nchi[u] := nchi[u] + nchi[p^.val] + 1;
end;
p := p^.link;
end;
end;
procedure precom;
var
i,t: longint;
begin
sort1(1,n);
for i := 1 to n do s[i] := i;
tmp := h;
for i := 1 to n do tmppos[i] := i;
sort2(1,n);
t := 1; h[tmppos[1]] := 1;
for i := 2 to n do
begin
if tmp[i] > tmp[i - 1] then inc(t);
h[tmppos[i]] := t;
end;
for i := 1 to n do idpos[id[i]] := i;
//Find boss
for i := 1 to n do a[i] := nil;
for i := 1 to maxn do tx[i] := maxv;
fillchar(pre, sizeof(pre), 0);
fillchar(nchi, sizeof(nchi), 0);
for i := n downto 1 do
begin
t := calc(h[i]);
if t <> maxv then
begin
pre[i] := t;
add(t,i);
end;
update(h[i],i);
end;
fillchar(free, sizeof(free), true);
for i := 1 to n do if free[i] then DFS(i);
end;
procedure query;
var
i,t: longint;
begin
for i := 1 to q do
begin
readln(fi, t);
t := idpos[t];
if pre[t] = 0 then write(fo, 0) else write(fo, id[pre[t]]);
writeln(fo, ' ', nchi[t]);
end;
end;
begin
openfile;
readln(fi, nTest);
for i := 1 to nTest do
begin
init;
precom;
query;
end;
closefile;
end.