結果

問題 No.121 傾向と対策：門松列（その２）
ユーザー gigurururugigurururu
提出日時 2015-01-09 20:39:14
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 3,697 ms / 5,000 ms
コード長 998 bytes
コンパイル時間 99 ms
コンパイル使用メモリ 76,920 KB
実行使用メモリ 333,108 KB
最終ジャッジ日時 2024-06-28 18:35:21
合計ジャッジ時間 11,936 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 164 ms
93,312 KB
testcase_01 AC 219 ms
106,340 KB
testcase_02 AC 100 ms
79,256 KB
testcase_03 AC 969 ms
318,472 KB
testcase_04 AC 3,697 ms
308,276 KB
testcase_05 AC 1,048 ms
323,916 KB
testcase_06 AC 1,247 ms
333,108 KB
testcase_07 AC 1,676 ms
317,932 KB
testcase_08 AC 1,468 ms
328,496 KB
権限があれば一括ダウンロードができます

ソースコード

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