結果

問題 No.956 Number of Unbalanced
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:57:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,698 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 193 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 64,376 KB
最終ジャッジ日時 2025-04-09 20:59:44
合計ジャッジ時間 4,229 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    A = list(map(int, input[1:n+1]))
    
    from collections import defaultdict
    pos_dict = defaultdict(list)
    for idx, num in enumerate(A):
        pos_dict[num].append(idx)
    
    total = 0
    
    for x in pos_dict:
        transformed = []
        for num in A:
            if num == x:
                transformed.append(1)
            else:
                transformed.append(-1)
        
        prefix_sums = [0]
        for t in transformed:
            prefix_sums.append(prefix_sums[-1] + t)
        
        sorted_ps = sorted(set(prefix_sums))
        rank = {v: i+1 for i, v in enumerate(sorted_ps)}
        
        max_rank = len(sorted_ps) + 2
        class BIT:
            def __init__(self, size):
                self.size = size
                self.tree = [0]*(size+1)
            def update(self, idx, delta=1):
                while idx <= self.size:
                    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
        
        bit = BIT(max_rank)
        current_sum = 0
        bit.update(rank[0])
        cnt = 0
        
        for i in range(1, len(prefix_sums)):
            s = prefix_sums[i]
            target_rank = bisect.bisect_left(sorted_ps, s) 
            cnt += bit.query(target_rank)
            r = rank[s]
            bit.update(r)
        
        total += cnt
    
    print(total)

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