I used RSQ(Range Sum Query) to solve this problem, but got Wrong Answer. Everything seems to be OK and I don't know where is a mistake. Here is my code:

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
Program Stars;
Var N:Integer;
    RSQ:Array[1..32000] Of Integer;
    Levels:Array[0..14999] Of Integer;
    I,J,K,X,Y:LongInt;
Begin
  ReadLn(N);
  For I:=1 To N Do Begin
    ReadLn(X,Y);

    J:=X;K:=0;
    While J>=1 Do Begin
      K:=K+RSQ[J];
      J:=J-(J And ((J-1) Xor J));
    End;
    Inc(Levels[K]);

    While X<=32000 Do Begin
      Inc(RSQ[X]);
      X:=X+(X And ((X-1) Xor X));
    End;
  End;
  For I:=0 To N-1 Do WriteLn(Levels[I]);
End.

If you put the line "Inc(X);" after "ReadLn(X,Y)" and change all 32000 on 32001 it will be AC. Complexity of my algorithm is N*Log(M) where N is number of stars and M is maximal possible value of axis of the star. It works only 0.031 sec!

Edited by author 13.03.2005 15:07

Where can I found out more about RSQ?