ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1028. Stars

How I got TL while i'm using the binary tree
Posted by fadi.masalmah 16 Sep 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
Posted by Poochi 1 Jul 2015 11:15
x and y can be 0; but you are using a 1 indexed FenwickTree! so your update goes on indefinitely!