MooFest POJ

MooFest

POJ - 1990
高级数据结构p203
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 #define LL long long 
 8 const int maxn = 20010;
 9 
10 LL dis[maxn], cnt[maxn];
11 int n; 
12 
13 struct Cow{
14     int v, p;
15     bool operator < (const Cow& a)const{
16         return v < a.v;
17     }
18 }c[maxn];
19 
20 void init(){
21     memset(dis, 0, sizeof dis);
22     memset(cnt, 0, sizeof cnt);
23 }
24 LL sum(int i, LL *c){
25     LL res = 0;
26     for(; i; i -= i & -i) res += c[i];
27     return res;
28 }
29 void add(int i, int v, LL *c){
30     for(; i <= maxn; i += i & -i) c[i] += v;
31 }
32 int main(){
33     while(scanf("%d", &n) != EOF){
34         init();
35         for(int i = 1; i <= n; i++){
36             scanf("%d %d", &c[i].v, &c[i].p);
37         }
38         sort(c + 1, c + n + 1);
39         LL tot = 0, ans = 0;
40         for(int i = 1; i <= n; i++){
41             LL cnt1 = sum(c[i].p, cnt), sum1 = sum(c[i].p, dis);
42             LL cnt2 = i - 1 - cnt1, sum2 = tot - sum1;
43             ans += c[i].v * (cnt1 * c[i].p - sum1 + sum2 - cnt2 * c[i].p);
44             tot += c[i].p;
45             add(c[i].p, c[i].p, dis);
46             add(c[i].p, 1, cnt);
47         }
48         printf("%lld
", ans);
49     }
50     return 0;
51 }
View Code