結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline().strip())
    A = list(map(int, sys.stdin.readline().split()))
    
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (self.size + 2)
        
        def update(self, index, delta=1):
            while index <= self.size:
                self.tree[index] += delta
                index += index & -index
        
        def query(self, index):
            res = 0
            while index > 0:
                res += self.tree[index]
                index -= index & -index
            return res
    
    max_val = 2 * N + 2
    total = 0
    
    freq = defaultdict(list)
    for idx, num in enumerate(A):
        freq[num].append(idx)
    
    for x in freq:
        transformed = []
        for num in A:
            if num == x:
                transformed.append(1)
            else:
                transformed.append(-1)
        
        prefix = [0] * (N + 1)
        for i in range(N):
            prefix[i + 1] = prefix[i] + transformed[i]
        
        ft = FenwickTree(max_val)
        ft.update(prefix[0] + N + 1)
        count = 0
        
        for i in range(1, N + 1):
            sum_i = prefix[i]
            target = sum_i - 1
            res = ft.query(target + N + 1)
            count += res
            ft.update(sum_i + N + 1)
        
        total += count
    
    print(total)

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