きままにものづくり

日々の気付いたことなんかを書いてます。

POJ 1990 : MooFest

問題

距離xと値vを持つN個の要素が与えられる。max(v_i,v_j)\times|x_i-x_j|を全ての要素の組み合わせで算出し、その総和を求めよ。

解法

Binary Index Treeを使う。以下の記事を参考にした。
http://d.hatena.ne.jp/komiyam/20110223/1298457263
c1はx以下の数を示し、c2はx+1以上の数を示している。csは個数を保持し、xsは距離を保持している。

計算量

O(NlogX)
N : 要素数
X : 距離の最大値

コード


TLEするコード