|
|
вернуться в форум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? |
|
|