結果

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

ソースコード

diff # 

from collections import defaultdict
import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    A = list(map(int, input[1:n+1]))
    
    freq = defaultdict(int)
    for num in A:
        freq[num] += 1
    
    total = 0
    
    for x in freq:
        B = []
        for num in A:
            if num == x:
                B.append(1)
            else:
                B.append(-1)
        
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + B[i]
        
        # Compress prefix sums
        sorted_prefix = sorted(prefix)
        unique = sorted(list(set(prefix)))
        rank = {v: i+1 for i, v in enumerate(unique)}
        
        max_rank = len(unique)
        fenwick = [0] * (max_rank + 2)
        
        current_sum = 0
        
        def update(pos):
            while pos <= max_rank:
                fenwick[pos] += 1
                pos += pos & -pos
        
        def query(pos):
            res = 0
            while pos > 0:
                res += fenwick[pos]
                pos -= pos & -pos
            return res
        
        ans = 0
        for s in prefix:
            r = rank[s]
            ans += query(r - 1)
            update(r)
        
        total += ans
    
    print(total)

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