結果

問題 No.121 傾向と対策：門松列（その２）
コンテスト
ユーザー gigurururu
提出日時 2015-01-09 20:39:14
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 4,946 ms / 5,000 ms
コード長 998 bytes
コンパイル時間 415 ms
コンパイル使用メモリ 77,480 KB
実行使用メモリ 333,948 KB
最終ジャッジ日時 2025-03-25 14:59:35
合計ジャッジ時間 16,915 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#coding:utf-8
from itertools import groupby
class BIT:
    def __init__(self,n):self.n=n;self.buf=[0]*(n+1)
    def add(self,x,v):
        while x<=self.n:self.buf[x]+=v;x+=x&-x
    def sum(self,x):
        s=0
        while x>0:s+=self.buf[x];x&=x-1
        return s

n=input()
l=map(int,raw_input().split())
bl=BIT(n)#左にある値
br=BIT(n)#右にある値
#座標圧縮
z={j:i+1  for i,j in enumerate(sorted(set(l)))}
t=[z[v] for v in l]
#最初は全部右にある
for v in t:br.add(v,1)

cnt=0
for i,v in enumerate(t):
    bl.add(v,1)
    br.add(v,-1)
    #左右の自分より小さい数同士、大きい数同士を掛けた数がパターン数
    cnt+=bl.sum(v-1)*br.sum(v-1)+(i+1-bl.sum(v))*(n-i-1-br.sum(v))
#左右が同じ数になるパターンを引く 解説(http://ideone.com/qVicVL)の通り
keyfunc = lambda x:t[x]
for _,g in groupby(sorted(range(0,n),key=keyfunc),keyfunc):
    a=list(g)
    for i in range(1,len(a)):
        cnt-=i*(len(a)-i)*(a[i]-a[i-1]-1)
print cnt
0