結果

問題 No.121 傾向と対策：門松列（その２）
コンテスト
ユーザー gigurururu
提出日時 2015-01-09 16:27:50
言語 Ruby
(3.4.1)
結果
RE  
実行時間 -
コード長 811 bytes
コンパイル時間 87 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 139,364 KB
最終ジャッジ日時 2024-06-13 03:31:01
合計ジャッジ時間 8,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 3 TLE * 2 -- * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class BIT
def initialize n;@n=n;@buf=[0]*(n+1)end
def add x,v;(@buf[x]+=v;x+=x&-x)while x<=@n;end
def sum x;s=0;(s+=@buf[x];x&=x-1)while x>0;s;end
end
n=gets.to_i
l=gets.split.map(&:to_i)
bl=BIT.new n#左にある値
br=BIT.new n#右にある値
#座標圧縮
z=Hash[l.sort.uniq.map.with_index{|i,j|[i,j+1]}]
t=l.map{|v|z[v]}
#最初は全部右にある
t.each{|v|br.add v,1}

cnt=t.map.with_index{|v,i|
  bl.add v,1
  br.add v,-1
  #左右の自分より小さい数同士、大きい数同士を掛けた数がパターン数
  bl.sum(v-1)*br.sum(v-1)+(i+1-bl.sum(v))*(n-i-1-br.sum(v))
}.inject(:+)
#左右が同じ数になるパターンを引く 解説(http://ideone.com/qVicVL)の通り
cnt-=(0...n).group_by{|i|t[i]}.values.flat_map{|a|(1...a.size).map{|i|i*(a.size-i)*(a[i]-a[i-1]-1)}}.inject(:+)
p cnt
0