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

用树状数组写的为什么Time Limit Exceeded

Posted by 382784268 at 2013-04-11 15:52:00 on Problem 1656
program poj1656;
var a:array[1..100,1..100] of integer;
    c:array[1..100,1..100] of integer;
    i,j,t,x,y,l,code:integer;
    s,chx,chy,chl:string;
    ch:char;
function lowbit(i:integer):longint;
begin
     lowbit:=(-i) and i;
end;
procedure change(i,j,color:integer);
var x,y,delta:integer;
begin
     if a[i,j]=color then exit;
     a[i,j]:=color;
     if color=0 then delta:=-1
     else delta:=color;
     x:=i;y:=j;
     while x<=100 do
     begin
           y:=j;
           while y<=100 do
           begin
                c[x,y]:=c[x,y]+delta;
                y:=y+lowbit(y);
           end;
           x:=x+lowbit(x);
     end;
end;
function getsum(i,j :integer):longint;
var x,y:integer;
    sum:longint;
begin
    sum:=0;
    x:=i;
    y:=j;
    while x>0 do
    begin
         y:=j;
         while y>0 do
         begin
               sum:=sum+c[x,y];
               y:=y-lowbit(y);
         end;
         x:=x-lowbit(x);
    end;
    getsum:=sum;
end;
begin
      fillchar(c,sizeof(c),0);
      fillchar(a,sizeof(a),0);
      readln(t);
      while t>0 do
      begin
          dec(t);
          readln(s);
          ch:=s[1];
          i:=pos(' ',s);

          delete(s,1,i);
          i:=pos(' ',s);
          chx:=copy(s,1,i-1);
          delete(s,1,i);
          chy:=copy(s,1,i-1);
          delete(s,1,i);
          chl:=copy(s,1,length(s));
          val(chx,x,code);
          val(chy,y,code);
          val(chl,l,code);

          case ch of
          'B':begin
                  for i:=x to x+l-1 do
                      for j:=y to y+l-1 do
                         change(i,j,1);


              end;
          'W':begin
                  for i:=x to x+l-1 do
                      for j:=y to y+l-1 do
                          change(i,j,0);
              end;
          'T':begin


                 writeln(getsum(x+l-1,y+l-1)-getsum(x+l-1,y-1)-getsum(x-1,y+l-1)+getsum(x-1,y-1));
              end;
          end;

      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