結果

問題 No.956 Number of Unbalanced
ユーザー gew1fw
提出日時 2025-06-12 14:15:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,434 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 54,272 KB
最終ジャッジ日時 2025-06-12 14:15:43
合計ジャッジ時間 4,685 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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())
    A = list(map(int, sys.stdin.readline().split()))
    
    def count_unbalanced(x):
        B = [1 if a == x else -1 for a in A]
        prefix = [0] * (N + 1)
        for i in range(1, N+1):
            prefix[i] = prefix[i-1] + B[i-1]
        
        max_val = max(prefix)
        min_val = min(prefix)
        offset = -min_val
        size = max_val - min_val + 1
        
        from bisect import bisect_left
        fenwick = [0] * (size + 2)
        
        total = 0
        
        def update(idx, val):
            idx += 1
            while idx <= size +1:
                fenwick[idx] += val
                idx += idx & -idx
        
        def query(idx):
            idx += 1
            res = 0
            while idx > 0:
                res += fenwick[idx]
                idx -= idx & -idx
            return res
        
        update(prefix[0] + offset, 1)
        
        for j in range(1, N+1):
            s = prefix[j]
            cnt = query(s + offset - 1)
            total += cnt
            
            update(s + offset, 1)
        
        return total
    
    freq = defaultdict(int)
    for num in A:
        freq[num] += 1
    
    total = 0
    for x in freq:
        total += count_unbalanced(x)
    
    print(total)

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