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大学生程序设计竞赛训练》暑期课面向全球招生!

有没有人帮忙看一下,一直WA,可以测的数据都对了

Posted by Caitlyn at 2014-05-14 21:22:14 on Problem 2481
const
  maxn=100010;
type
  rec=record
        s,e,id:longint;
      end;
var
  a:array[1..maxn] of rec;
  ans,tree:array[1..maxn] of longint;
  n,i,j,s,e,maxs:longint;
  function getbit(x:longint):longint;
  begin
    exit(x and (-x));
  end;
  procedure qsort(l,r:longint);
  var
    i,j,mid:longint;
    tmp:rec;
  begin
    i:=l; j:=r; mid:=a[(l+r) div 2].e;
    repeat
      while a[i].e>mid do inc(i);
      while a[j].e<mid do dec(j);
      if a[i].e=a[j].e then
      begin
        if a[i].s>a[j].s then
        begin
          tmp:=a[i];
          a[i]:=a[j];
          a[j]:=tmp;
        end;
        inc(i);
        dec(j);
      end
      else
        if i<=j then
        begin
          tmp:=a[i];
          a[i]:=a[j];
          a[j]:=tmp;
          inc(i);
          dec(j);
        end;
    until i>j;
    if i<r then qsort(i,r);
    if l<j then qsort(l,j);
  end;
  function sum(x:longint):longint;
  var
    k:longint;
  begin
    k:=0;
    while x>0 do
    begin
      k:=k+tree[x];
      x:=x-getbit(x);
    end;
    exit(k);
  end;
  procedure add(x:longint);
  begin
    while x<=maxs do
    begin
      inc(tree[x]);
      x:=x+getbit(x);
    end;
  end;
  procedure work;
  var
    i,cnt:longint;
    tmp:rec;
  begin
    cnt:=0; tmp.s:=-1; tmp.e:=-1;
    for i:=1 to n do
    begin
      if (a[i].s=tmp.s) and (a[i].e=tmp.e) then inc(cnt)
      else
        begin
          cnt:=0;
          tmp.s:=a[i].s;
          tmp.e:=a[i].e;
        end;
      ans[a[i].id]:=sum(a[i].s)-cnt;
      add(a[i].s);
    end;
  end;
begin
  readln(n);
  while n<>0 do
  begin
    fillchar(tree,sizeof(tree),0);
    fillchar(ans,sizeof(ans),0);
    maxs:=0;
    for i:=1 to n do
    begin
      readln(s,e);
      inc(s);
      inc(e);
      a[i].s:=s;
      a[i].e:=e;
      a[i].id:=i;
      if a[i].s>maxs then maxs:=a[i].s;
    end;
    qsort(1,n);
    work;
    for i:=1 to n do write(ans[i],' ');
    writeln;
    readln(n);
  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