Hello, my code gives TLE using a Binary Indexed Tree, and I find the thing quite strange... Here is my solution:

#include <iostream>



using namespace std;



#define MAXX 32001



int tree[ MAXX ];

int l[ 15000 ];





inline void update( int x )

{

    while ( x <= MAXX )

    {

        tree[ x ]++;

        x += ( x & -x );

    }

}





inline int query( int x )
{
    int sum = 0;
    while ( x > 0 )
    {
        sum += tree[ x ];
        x -= ( x & -x );
    }
    return sum;
}





int main()

{

    int n, x, y;

    cin >> n;



    for ( int i = 0;  i < n;  i++ )

    {

        scanf( "%d %d", &x, &y );

        l[ query( x ) ]++;


        update( x );

    }



    for ( int i = 0;  i < n;  i++ )

        printf( "%d\n", l[ i ] );

}

while ( x > 0 )
{
sum += tree[ x ];
x -= ( x & -x );
}
-
Your prog should be work incorrectly with x = 0.
Try x++, y++ after scanf.

Explain me, please, why this program works correctly

I received AC using algo O(n^1.5). Who can explain me solution O(n*log(n))?

give your e-mail

Thank you, that saved me ;)

I got AC when add x++; and y++;

is this solution using one dimensional Fenwick? why it works?

=> coordinat y's not needed!

UPD: "Stars with equal Y coordinates are listed in ascending order of X coordinate." thanks

Edited by author 14.01.2011 15:47

Edited by author 14.01.2011 15:52

its my TLE3 solution:
2D Fenwik + RB tree (map)

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int N = 0,M = 0;
map<int,map<int,int> > Btree;
int rsq(int x,int y)
{
    int res = 0;
    while(x >= 0)
    {
        int i = y;
        while(i >= 0)
        {
            res += Btree[x][i];
            i = (i & (i + 1)) - 1;
        }
        x = (x & (x + 1)) - 1;
    }
    return res;
}
void upd(int x,int y,int d)
{

    while(x < M)
    {
        int i = y;
        while(i < N)
        {
            Btree[x][i] += d;
            i = i | (i + 1);
        }
        x = x | (x + 1);
    }
}
bool cond(pair<int,int> a,pair<int,int> b)
{
    return a.second < b.second;
}
int res[15001] = {0};
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    scanf("%d",&n);
    vector<pair<int,int> > mp;
    for(int i = 0; i < n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        M = max(M,x);
        N = max(N,y);
        x--;
        y--;
        mp.push_back(make_pair(x,y));
    }
    for(int i = 0; i < n; i++)
        upd(mp[i].first,mp[i].second,1);

    for(int i = 0; i < n; i++)
    {
        res[rsq(mp[i].first,mp[i].second)]++;
    }
    for(int i = 1; i <= n; i++)
    {
        printf("%d\n",res[i]);
    }
    return 0;
}