結果

問題 No.956 Number of Unbalanced
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:31:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 847 bytes
コンパイル時間 463 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 107,648 KB
最終ジャッジ日時 2025-06-12 20:32:52
合計ジャッジ時間 4,191 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N, *rest = list(map(int, sys.stdin.read().split()))
    A = rest[:N]

    unique_x = list(set(A))
    total = 0

    for x in unique_x:
        transformed = [1 if num == x else -1 for num in A]
        prefix = [0] * (len(transformed) + 1)
        for i in range(len(transformed)):
            prefix[i+1] = prefix[i] + transformed[i]

        fenwick = defaultdict(int)
        fenwick[0] = 1
        res = 0

        for i in range(1, len(prefix)):
            current = prefix[i]
            cnt = 0
            for key in fenwick:
                if key < current:
                    cnt += fenwick[key]
            res += cnt

            fenwick[prefix[i]] += 1

        total += res

    print(total)

if __name__ == '__main__':
    main()
0