結果

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

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    n, *rest = map(int, sys.stdin.read().split())
    A = rest[:n]

    total = 0

    freq = defaultdict(int)
    for num in A:
        freq[num] += 1

    for x in freq:
        S = [0] * (n + 1)
        for i in range(1, n + 1):
            S[i] = S[i-1] + (1 if A[i-1] == x else -1)

        counts = defaultdict(int)
        counts[0] = 1
        res = 0
        for r in range(1, n + 1):
            current = S[r]
            left = current - 1
            cnt = 0
            while left >= -r:
                if left in counts:
                    cnt += counts[left]
                left -= 1
            res += cnt
            counts[current] = counts.get(current, 0) + 1
        total += res

    print(total)

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