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.

Download