poj 1990 MooFest

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