結果

問題 No.694 square1001 and Permutation 3
ユーザー lam6er
提出日時 2025-03-31 17:36:40
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,473 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 258,480 KB
最終ジャッジ日時 2025-03-31 17:37:26
合計ジャッジ時間 7,960 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 MLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left

def main():
    sys.setrecursionlimit(1 << 25)
    n = int(sys.stdin.readline())
    A = [int(sys.stdin.readline()) for _ in range(n)]
    
    if n == 0:
        return
    
    # Coordinate compression and prepare sorted_unique
    sorted_unique = sorted(set(A))
    sorted_unique.sort()
    m = len(sorted_unique)
    
    # Frequency dictionary
    freq = {}
    for num in A:
        if num in freq:
            freq[num] += 1
        else:
            freq[num] = 1
    
    # Build prefix_counts for elements_less calculation
    prefix_counts = []
    current = 0
    for num in sorted_unique:
        current += freq[num]
        prefix_counts.append(current)
    
    # Precompute X and Y for each element in A
    X = []
    Y = []
    for num in A:
        # Compute elements_less
        idx = bisect_left(sorted_unique, num) - 1
        elements_less = prefix_counts[idx] if idx >= 0 else 0
        
        # Compute elements_greater
        count_num = freq[num]
        elements_greater = n - elements_less - count_num
        
        X.append(elements_less)
        Y.append(elements_greater)
    
    # Compute initial inversion count using Fenwick Tree
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (self.size + 2)  # 1-based indexing
        
        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
    
    # Create a rank map for coordinate compression
    rank_map = {num: i+1 for i, num in enumerate(sorted_unique)}  # 1-based ranks
    max_rank = len(sorted_unique)
    
    ft = FenwickTree(max_rank)
    inv_initial = 0
    
    for i in reversed(range(n)):
        num = A[i]
        current_rank = rank_map[num]
        # Number of elements already in the tree (to the right) that are less than current_num
        cnt = ft.query(current_rank - 1)
        inv_initial += cnt
        ft.update(current_rank)
    
    # Compute answers
    ans = [0] * n
    ans[0] = inv_initial
    for k in range(1, n):
        ans[k] = ans[k-1] - X[k-1] + Y[k-1]
    
    # Output the answers
    for val in ans:
        print(val)

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