結果

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

ソースコード

diff # 

import bisect
from collections import defaultdict

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # Using 1-based indexing
    
    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx
    
    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    A = list(map(int, input[1:n+1]))
    
    freq = defaultdict(list)
    for idx, num in enumerate(A):
        freq[num].append(idx)
    
    total = 0
    for x in freq:
        positions = set(freq[x])
        D = [0]  # D[0] = 0
        current = 0
        for i in range(n):
            if i in positions:
                current += 1
            else:
                current -= 1
            D.append(current)
        
        # Compress the D values
        sorted_values = sorted(set(D))
        ft_size = len(sorted_values)
        ft = FenwickTree(ft_size)
        inv_count = 0
        
        for d in D:
            # Find the number of elements < d in the compressed sorted_values
            cnt = bisect.bisect_left(sorted_values, d)
            inv_count += ft.query(cnt)
            # Insert the current d into the Fenwick Tree
            pos = bisect.bisect_left(sorted_values, d) + 1  # 1-based index
            if pos <= ft_size:
                ft.update(pos, 1)
        
        total += inv_count
    
    print(total)

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