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]
感想
最近構造体を使いたい病にかかっているので何故か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; }