ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1028. Звёзды

Alexander Bovkun What is wrong with my code? [2] // Задача 1028. Звёзды 7 мар 2005 23:37
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.
Alexander Bovkun I have made a little error... [1] // Задача 1028. Звёзды 13 мар 2005 15:06
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
Olzhas2dy Re: I have made a little error... // Задача 1028. Звёзды 13 июн 2007 17:36
Where can I found out more about RSQ?