poj 2481 Cows

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=100000+5;
 6 int c[maxn];
 7 int ans[maxn];
 8 struct pos
 9 {
10     int s,e;
11     int id;
12     bool operator <(const pos &a)const
13     {
14         if(a.e==e) return a.s>s;
15         return a.e<e;
16     }
17 }p[maxn];
18 int lowbit(int x)
19 {
20     return x&-x;
21 }
22 int sum(int x)
23 {
24     int ret=0;
25     while(x>0)
26     {
27         ret+=c[x];
28         x-=lowbit(x);
29     }
30     return ret;
31 }
32 void add(int x,int inc)
33 {
34     while(x<=maxn)
35     {
36         c[x]+=inc;
37         x+=lowbit(x);
38     }
39 }
40 int main()
41 {
42     int n;
43     while(scanf("%d",&n)!=EOF&&n)
44     {
45         memset(c,0,sizeof(c));
46         for(int i=0;i<n;i++)
47             {
48                 scanf("%d%d",&p[i].s,&p[i].e);
49                 p[i].id=i+1;
50             }
51         sort(p,p+n);
52         ans[p[0].id]=0;
53         add(p[0].s+1,1);
54         for(int i=1;i<n;i++)
55         {
56                 if(p[i].s==p[i-1].s&&p[i].e==p[i-1].e)
57                     ans[p[i].id]=ans[p[i-1].id];
58                 else
59                 ans[p[i].id]=sum(p[i].s+1);
60                 add(p[i].s+1,1);
61         }
62         printf("%d",ans[1]);
63         for(int i=2;i<=n;i++)
64             printf(" %d",ans[i]);
65         printf("
");
66     }
67     return 0;
68 }