Algoogle

Algorithm for Programming Contest

PKU 1990 MooFest

Category: PKU Tag: binary-indexed-tree

MooFest

問題概要


各牛に場所xと聞こえる音量vが与えられるとき,

を求めよ.

解法


vの小さい牛から順に, その牛よりvの小さい牛について
左にいる牛の数とその距離の総和, 右にいる牛の数とその距離の総和が出せれば, 距離の差を取ってvをかければその牛のvを使うものの総和が出せる.
これをBITを用いることで計算する.
各x座標についてそこまでの牛の数の和についてのBITと距離の和についてのBITを用いればよい.

コード


(1990.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <algorithm>
#include <cstdio>
#include <map>
#include <iostream>

#define int long long

using namespace std;

typedef pair<int,int> pii;

int N, bit[2][20010];
pii cow[20010];

void add(int i, int x, int m){
    while(i <= 20000){
        bit[m][i] += x;
        i += i & -i;
    }
}

int sum(int i, int m){
    int ret = 0;
    while(i > 0){
        ret += bit[m][i];
        i -= i & -i;
    }
    return ret;
}

signed main(){
    scanf("%lld", &N);
    for(int i = 0; i < N; i++){
        int v, x; scanf("%lld%lld", &v, &x);
        cow[i] = pii(v,x);
    }
    sort(cow, cow+N);
    int ans = 0;
    for(int i = 0; i < N; i++){
        int lc = sum(cow[i].second, 0), ld = sum(cow[i].second, 1);
        int rc = sum(20000, 0) - lc, rd = sum(20000, 1) - ld;
        ans += cow[i].first * (cow[i].second*lc - ld + rd - cow[i].second*rc);
        add(cow[i].second, 1, 0);
        add(cow[i].second, cow[i].second, 1);
    }
    printf("%lld\n", ans);
    return 0;
}

Comments