0.031s 312KB C++ sulotion

I've been stuck in this problem for a very long time, but today I got the idea of Binary Indexed Tree from wikipedia and finally solved this problem :)

Binary Indexed Tree,or BIT, can be viewed as a simplified version of Segment Tree,easier to code and less function to perform. But It's enough to solve this problem

#include<iostream>

#include<cstdio>

using namespace std;

const int Max = 32005;

int n;

int c[Max] = {0};

int level[Max] = {0};

int lowbit(int x)

{

return x&(-x);

}

int sum(int i)

{

int s = 0;

while(i > 0)

{

s += c[i];

i -= lowbit(i);

}

return s;

}

void update(int pos,int val)

{

while(pos <= Max)

{

c[pos] += val;

pos += lowbit(pos);

}

}

int main()

{

scanf("%d",&n);

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

{

int x,y;

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

x ++;

level[ sum(x) ] ++;

update(x,1);

}

for(int i = 0; i < n; i ++) printf("%d\n",level[i]);

}

Re: 0.031s 312KB C++ sulotion

How can this even be correct if you don't use the y-coordinates at all?

Re: 0.031s 312KB C++ sulotion

Posted by

Abzal 10 Jul 2012 00:54

Because in statement there was written that y-coordinates are already sorted

Re: 0.031s 312KB C++ sulotion

in function main,why you use "x ++"?

Re: 0.031s 312KB C++ sulotion

cose in problem x in [0,32000 ]

so 0 is bad value for binary :)

so we just shift all x on some const ( just 1) so all value between 1 and power(2,someN)

Re: 0.031s 312KB C++ sulotion

Why do you use 32005 as a size of an array?

Re: 0.031s 312KB C++ sulotion

Because it is given in constraint. That x and y values will be less than 32000.