結果

問題 No.121 傾向と対策：門松列（その２）
ユーザー gigurururugigurururu
提出日時 2015-01-09 20:39:14
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 4,746 ms / 5,000 ms
コード長 998 bytes
コンパイル時間 1,553 ms
コンパイル使用メモリ 77,416 KB
実行使用メモリ 329,656 KB
最終ジャッジ日時 2023-09-11 04:04:02
合計ジャッジ時間 15,040 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 200 ms
94,812 KB
testcase_01 AC 262 ms
107,320 KB
testcase_02 AC 115 ms
80,848 KB
testcase_03 AC 1,286 ms
313,284 KB
testcase_04 AC 4,746 ms
305,204 KB
testcase_05 AC 1,336 ms
326,096 KB
testcase_06 AC 1,496 ms
329,656 KB
testcase_07 AC 1,902 ms
313,116 KB
testcase_08 AC 1,848 ms
327,808 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