Hatena::ブログ(Diary)

komiyamの日記

2011-02-23

POJ-1990: MooFest

keyword

BIT C++

問題概要

(x,v) in [1..X]*[1..V] (X,V<2*10^4)の点がN(<2*10^4)個与えられる。Σ max(v[i],v[j])*|x[i]-x[j]|を求める問題。

解法

maxとか処理が面倒なのでvをキーにして昇順にソートする。求めるのはΣ_{∀i with v[i]<v[j]} v[j]*|x[i]-x[j]|なので、これは更にΣ_{∀i with v[i]<v[j] and x[i]<x[j]} v[j]*(x[j]-x[i]) + Σ_{∀i with v[i]<v[j] and x[j]<x[i]} v[j]*(x[i]-x[j])となる。これはBITを使って個数と距離を加えていけばO(log X)で計算できる。詳細はソース参照のこと。

感想

最近構造体を使いたい病にかかっているので何故かpairを使うという発想が出なかった。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int64;

struct moo{
    int pos, vol;
    moo(int _p, int _v):pos(_p),vol(_v){}
    moo(){moo(0,0);}
};

bool operator<(const moo& a, const moo& b){ return a.vol < b.vol; }

const int MAX_N = 20009;
const int MAX_X = 20009;
moo ms[MAX_N];
int N;
int64 dists[MAX_X];
int64 cnts[MAX_X];

int64 sum(int64 as[MAX_X], int n){
    int64 ret = 0;
    for(;n;n-=n&-n) ret += as[n];
    return ret;
}

//sum in range[from, to)
int64 sum(int64 as[MAX_X], int from, int to){
    return sum(as,to-1) - sum(as,from-1);
}

void add(int64 as[MAX_X], int n, int x){
    for(;n<=MAX_X-1;n+=n&-n)as[n]+=x;
}

int64 solve(){
    sort(ms,ms+N);
    int64 ans = 0;
    for(int i=0; i<N; i++){
        int v = ms[i].vol, x = ms[i].pos;
        int64 c1 = sum(cnts,1,x), c2 = sum(cnts,x+1,MAX_X);
        ans += v*( (c1*x - sum(dists,1,x)) + (sum(dists,x+1,MAX_X) - c2*x) );
        add(cnts,x,1);
        add(dists,x,x);
    }
    return ans;
}

int main(){
    scanf("%d",&N);
    for(int i=0; i<N; i++){
        int x,v;
        scanf("%d%d",&v,&x);
        ms[i] = moo(x,v);
    }
    printf("%lld\n",solve());
    return 0;
}

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/komiyam/20110223/1298457263