poj2352 Stars

http://poj.org/problem?id=2352
 1 #include <cstdio>
 2 #include <cstring>
 3 #define maxn 400000
 4 using namespace std;
 5 
 6 int c[maxn],leve[maxn],a,b,n;
 7 
 8 int lowbit(int x)
 9 {
10     return x&(x^(x-1));
11 }
12 
13 void add(int x,int m)
14 {
15     while(x<=maxn)
16     {
17         c[x]+=m;
18         x+=lowbit(x);
19     }
20 }
21 
22 int sum(int x)
23 {
24     int sum1=0;
25     while(x>0)
26     {
27         sum1+=c[x];
28         x-=lowbit(x);
29     }
30     return sum1;
31 }
32 int main()
33 {
34     scanf("%d",&n);
35     memset(c,0,sizeof(c));
36     for(int k=1; k<=n; k++)
37     {
38         scanf("%d%d",&a,&b);
39         a++;
40         int t=sum(a);
41         leve[t]++;
42         add(a,1);
43     }
44     for(int i=0; i<n; i++)
45     {
46         printf("%d
",leve[i]);
47     }
48     return 0;
49 }
View Code