|
|
back to boardTL with O(N*logN) solution!...Please give some tips to make it more effective Posted by maksay 11 Dec 2007 00:30 Var s:array[0..32000] of integer;
a:array[0..15000] of integer;
x,y,i,n,r,k:Integer;
begin
Readln(n);
For i:=1 to n do
begin
Readln(x,y);
k:=x;
r:=0;
While (k>0) do
begin
r:=r+s[k];
k:=(k and (k-1));
end;
r:=r+s[0];
Inc(a[r]);
While x<=32000 do
begin
s[x]:=s[x]+1;
x:=(x shl 1)-(x and (x-1));
end;
end;
For i:=0 to n-1 do
Writeln(a[i]);
end. Re: TL with O(N*logN) solution!...Please give some tips to make it more effective Posted by =HPF= 12 Mar 2008 19:10 This is binary indexed tree.
Did you think about "0"？ 0 and AnyNum = 0 ... Re: TL with O(N*logN) solution!...Please give some tips to make it more effective try replace interger with longint.
edit:
Oh, yes problem with 0. your code not go to the right.
x = (x shl 1) - (x and (x - 1));
if (x = 0) then x = 0;
Edited by author 13.03.2008 19:26 |
|
|
