結果

問題 No.121 傾向と対策：門松列（その２）
ユーザー rpy3cpprpy3cpp
提出日時 2015-07-14 01:11:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,055 ms / 5,000 ms
コード長 1,560 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 87,040 KB
実行使用メモリ 313,680 KB
最終ジャッジ日時 2023-09-11 04:06:29
合計ジャッジ時間 8,095 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 159 ms
94,272 KB
testcase_01 AC 198 ms
107,652 KB
testcase_02 AC 107 ms
78,060 KB
testcase_03 AC 770 ms
260,264 KB
testcase_04 AC 2,055 ms
313,680 KB
testcase_05 AC 762 ms
260,316 KB
testcase_06 AC 729 ms
263,924 KB
testcase_07 AC 764 ms
260,660 KB
testcase_08 AC 825 ms
260,120 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compress(As):
    '''とびとびの値のリストを連続する値のリストに変換する。
    '''
    val2idx = {a: i for i, a in enumerate(sorted(set(As)))}
    return [val2idx[a] for a in As]

def add_count_f(val, data, size):
    '''セグメントツリーへの要素 val を追加し、
    val 未満の要素の個数と、val 超の要素の個数を返す。
    '''
    pos = size + val
    count = 0
    while pos:
        if pos & 1:
            count += data[pos-1]
        data[pos] += 1
        pos >>= 1
    return count, data[1] - count - data[size + val]

def count_aba2(As):
    maxA = max(As)
    freq = [-1] * (maxA + 1)
    for a in As:
        freq[a] += 1
    posList = {i:[] for i in range(maxA + 1) if freq[i]}
    for i, a in enumerate(As):
        if freq[a]:
            posList[a].append(i)
    count = 0
    for poss in posList.values():
        n = len(poss)
        for i in range(1, n):
            count += (poss[i] - poss[i-1] - 1) * i * (n-i)
    return count


N = int(input())
As = compress(list(map(int, input().split())))
size = 1 << (len(bin(N)) - 2)
segL = [0] * (size * 2)
segR = [0] * (size * 2)
belowL = [0] * N
aboveL = [0] * N
result = 0
for i, a in enumerate(As):
    below, above = add_count_f(a, segL, size)
    belowL[i] = below
    aboveL[i] = above
for i, a in enumerate(As[::-1], 1):
    belowR, aboveR = add_count_f(a, segR, size)
    result += belowL[-i] * belowR + aboveL[-i] * aboveR

# 左右が同じ値の疑似門松列の個数を差し引く
result -= count_aba2(As)
print(result)
0