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 wukewen at 2013-10-30 22:12:32 on Problem 2481
//第一次sort是s的降序,第二次是相同s中的e升序
var
  a,b,c,f,print,t,p:array[0..100010] of longint;
  n,i,j,k,l,s,x,y,max,ta,tb:longint;
procedure swap(var a,b:longint);
  var
    c:longint;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;
procedure up(dep:longint);
  begin
  if dep=1 then exit;
  if a[dep]>=a[dep div 2] then
     begin
     swap(a[dep],a[dep div 2]);
     swap(b[dep],b[dep div 2]);
     swap(c[dep],c[dep div 2]);
     up(dep div 2);
     end;
  end;
procedure down(dep:longint);
  begin
  if dep*2>n-i then exit;
  if dep*2=n-i then
     begin
     if a[dep]<=a[dep*2] then
        begin
        swap(a[dep],a[dep*2]);
        swap(b[dep],b[dep*2]);
        swap(c[dep],c[dep*2]);
        end;
     exit;
     end;
  if a[dep*2]>a[dep*2+1] then
     begin
     if a[dep]<=a[dep*2] then
        begin
        swap(a[dep],a[dep*2]);
        swap(b[dep],b[dep*2]);
        swap(c[dep],c[dep*2]);
        down(dep*2);
        end;
     end
                         else
     begin
     if a[dep]<=a[dep*2+1] then
        begin
        swap(a[dep],a[dep*2+1]);
        swap(b[dep],b[dep*2+1]);
        swap(c[dep],c[dep*2+1]);
        down(dep*2+1);
        end;
     end;
  end;
procedure up1(dep:longint);
  begin
  if dep=1 then exit;
  if t[dep]>=t[dep div 2] then
     begin
     swap(t[dep],t[dep div 2]);
     swap(p[dep],p[dep div 2]);
     up1(dep div 2);
     end;
  end;
procedure down1(dep:longint);
  begin
  if dep*2>t[0] then exit;
  if dep*2=t[0] then
     begin
     if t[dep]<=t[dep*2] then
        begin
        swap(t[dep],t[dep*2]);
        swap(p[dep],p[dep*2]);
        end;
     exit;
     end;
  if t[dep*2]>t[dep*2+1] then
     begin
     if t[dep]<=t[dep*2] then
        begin
        swap(t[dep],t[dep*2]);
        swap(p[dep],p[dep*2]);
        down1(dep*2);
        end;
     end
                         else
     begin
     if t[dep]<=t[dep*2+1] then
        begin
        swap(t[dep],t[dep*2+1]);
        swap(p[dep],p[dep*2+1]);
        down1(dep*2+1);
        end;
     end;
  end;
begin
  readln(n);
  while n<>0 do
    begin
    max:=-1;
    for i:=1 to n do
      begin
      readln(a[i],b[i]);
      inc(a[i]);
      inc(b[i]);
      c[i]:=i;
      if b[i]>max then max:=b[i];
      up(i);
      end;
    for i:=1 to n do
      begin
      swap(a[1],a[n-i+1]);
      swap(b[1],b[n-i+1]);
      swap(c[1],c[n-i+1]);
      down(1);
      end;
    ta:=a[1];
    i:=1;
    j:=1;
    while i<=n do
      begin
      while (i<=n)and(a[i]=ta) do inc(i);
      dec(i);
      t[0]:=0;
      for k:=j to i do
        begin
        inc(t[0]);
        t[t[0]]:=b[k];
        p[t[0]]:=c[k];
        up1(t[0]);
        end;
      for k:=j to i do
        begin
        b[k]:=t[1];
        c[k]:=p[1];
        t[1]:=t[t[0]];
        p[1]:=p[t[0]];
        dec(t[0]);
        down1(1);
        end;
      inc(i);
      ta:=a[i];
      j:=i;
      end;
    fillchar(f,sizeof(f),0);
    fillchar(print,sizeof(print),0);
    ta:=-1;
    tb:=-1;
    for i:=1 to n do
    if (a[i]=ta)and(b[i]=tb) then
       begin
       print[c[i]]:=print[c[i-1]];
       x:=b[i];
       inc(f[x]);
       while x<max do
         begin
         inc(f[x+(x and -x)]);
         x:=x+(x and -x);
         end;
       end
       else
      begin
      ta:=a[i];
      tb:=b[i];
      x:=max;
      inc(print[c[i]],f[x]);
      while x>0 do
        begin
        inc(print[c[i]],f[x-(x and -x)]);
        x:=x-(x and -x);
        end;
      x:=b[i]-1;
      dec(print[c[i]],f[x]);
      while x>0 do
        begin
        dec(print[c[i]],f[x-(x and -x)]);
        x:=x-(x and -x);
        end;
      x:=b[i];
      inc(f[x]);
      while x<max do
        begin
        inc(f[x+(x and -x)]);
        x:=x+(x and -x);
        end;
      end;
    write(print[1]);
    for i:=2 to n do
      write(' ',print[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