結果

問題 No.956 Number of Unbalanced
ユーザー gew1fw
提出日時 2025-06-12 21:08:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,184 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 55,596 KB
最終ジャッジ日時 2025-06-12 21:09:34
合計ジャッジ時間 4,869 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
    from collections import defaultdict

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

    total = 0

    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (self.size + 2)
        
        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

    for x in pos:
        occ = pos[x]
        S = [0] * (N + 1)
        cnt = 0
        ptr = 0
        for i in range(1, N + 1):
            if ptr < len(occ) and i == occ[ptr]:
                cnt += 1
                ptr += 1
            S[i] = cnt
        T = [2 * S[i] - i for i in range(N + 1)]
        all_values = []
        for t in T:
            all_values.append(t)
            all_values.append(t - 1)
        sorted_unique = sorted(set(all_values))
        rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
        max_rank = len(sorted_unique)
        ft = FenwickTree(max_rank)
        res_x = 0
        ft.update(rank[T[0]])
        for j in range(1, N + 1):
            current_T = T[j]
            target = current_T - 1
            left = 0
            right = len(sorted_unique) - 1
            best = -1
            while left <= right:
                mid = (left + right) // 2
                if sorted_unique[mid] <= target:
                    best = mid
                    left = mid + 1
                else:
                    right = mid - 1
            if best != -1:
                res_x += ft.query(rank[sorted_unique[best]])
            else:
                res_x += 0
            current_rank = rank[current_T]
            ft.update(current_rank)
        total += res_x
    print(total)

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