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

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

How I got TL while i'm using the binary tree
Послано fadi.masalmah 16 сен 2014 00:19
I got TL although i'm using the binary tree , and when I looked for a solution on the net i found the same of mine but in another words
here is my code:

#include <cstdio>
#include <cstring>

using namespace std;
#define max 32002
int a[max];
void update(int i,int n,int v)
{
    while(i<=n)
    {
        a[i]+=v;
        i+=i&(-i);
    }

}
int read(int i)
{
    int v=0;
    while(i>0)
    {
        v+=a[i];
        i-=i&(-i);
    }
    return v;

}

int main()
{
    int n;
    scanf("%d",&n);

    int b[15010];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);


        b[read(x)]++;
        update(x,32002,1);
    }
    for(int i=0;i<n;i++)
        printf("%d \n",b[i]);
    return 0;
}

so please help me cause i'm about to lose my mind!!!
Re: How I got TL while i'm using the binary tree
Послано Poochi 1 июл 2015 11:15
x and y can be 0; but you are using a 1 indexed FenwickTree! so your update goes on indefinitely!