Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

1000MS,我也是醉了,C++和PASCAL差这么远吗

Posted by Caitlyn at 2016-05-09 20:53:22 on Problem 2828
const
  maxn=200000;
type
  rec=record
        pos,val:longint;
      end;
var
  sum,ans:array[1..maxn shl 2] of longint;
  person:array[1..maxn] of rec;
  n,i:longint;
  procedure update(i,l,r,pos,val:longint);
  var
    mid:longint;
  begin
    if l=r then
    begin
      ans[i]:=val;
      dec(sum[i]);
      exit;
    end;
    mid:=(l+r) div 2;
    if pos<=sum[i*2] then update(i*2,l,mid,pos,val)
    else update(i*2+1,mid+1,r,pos-sum[i*2],val);
    sum[i]:=sum[i*2]+sum[i*2+1];
  end;
  procedure buildtree(i,l,r:longint);
  var
    mid:longint;
  begin
    sum[i]:=r-l+1;
    if l=r then exit;
    mid:=(l+r) div 2;
    buildtree(i*2,l,mid);
    buildtree(i*2+1,mid+1,r);
  end;
  procedure print(i,l,r:longint);
  var
    mid:longint;
  begin
    if l=r then begin write(ans[i],' '); exit; end;
    mid:=(l+r) div 2;
    print(i*2,l,mid);
    print(i*2+1,mid+1,r);
  end;
begin
  while not eof do
  begin
    readln(n);
    if n=0 then break;
    for i:=1 to n do readln(person[i].pos,person[i].val);
    buildtree(1,1,n);
    for i:=n downto 1 do update(1,1,n,person[i].pos+1,person[i].val);
    print(1,1,n);
    writeln;
  end;
end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator