結果

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

ソースコード

diff #
raw source code 

import sys
from bisect import bisect_left

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

    from collections import defaultdict
    pos = defaultdict(list)
    for idx, num in enumerate(A):
        pos[num].append(idx + 1)  # 1-based

    total = 0

    for x in pos:
        occurrences = pos[x]
        prefix = [0] * (len(occurrences) + 1)
        ptr = 0
        current_cnt = 0
        transformed = []
        for i in range(1, N + 1):
            if ptr < len(occurrences) and i == occurrences[ptr]:
                current_cnt += 1
                ptr += 1
            t = 2 * current_cnt - i
            transformed.append(t)
        transformed = [0] + transformed  # add t[0] = 0

        # Coordinate compression
        sorted_ts = sorted(set(transformed))
        rank = {v: i+1 for i, v in enumerate(sorted_ts)}  # 1-based indexing for Fenwick

        ft_size = len(sorted_ts)
        ft = [0] * (ft_size + 2)

        def fenwick_update(idx):
            while idx <= ft_size:
                ft[idx] += 1
                idx += idx & -idx

        def fenwick_query(idx):
            res = 0
            while idx > 0:
                res += ft[idx]
                idx -= idx & -idx
            return res

        for t in transformed:
            r = bisect_left(sorted_ts, t)
            cnt = fenwick_query(r)
            total += cnt
            compressed = rank[t]
            fenwick_update(compressed)

    print(total)

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