結果

問題 No.694 square1001 and Permutation 3
ユーザー lam6er
提出日時 2025-03-20 20:48:59
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,677 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 279,876 KB
最終ジャッジ日時 2025-03-20 20:49:21
合計ジャッジ時間 9,230 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 MLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    A = list(map(int, data[1:n+1]))
    
    # Coordinate compression for Fenwick Tree
    sorted_unique = sorted(set(A))
    compress = {v: i + 1 for i, v in enumerate(sorted_unique)}
    max_rank = len(compress)
    
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (self.size + 1)
        
        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
    
    ft = FenwickTree(max_rank)
    inv = 0
    for i in reversed(range(n)):
        x = A[i]
        rank = compress[x]
        inv += ft.query(rank - 1)
        ft.update(rank)
    
    sorted_A = sorted(A)
    count_less = []
    count_greater = []
    for x in A:
        cl = bisect.bisect_left(sorted_A, x)
        cg = len(sorted_A) - bisect.bisect_right(sorted_A, x)
        count_less.append(cl)
        count_greater.append(cg)
    
    right_rotations = [inv]
    for i in reversed(range(n-1)):
        x = A[i+1]
        cl = count_less[i+1]
        cg = count_greater[i+1]
        new_inv = right_rotations[-1] - cg + cl
        right_rotations.append(new_inv)
    
    output = []
    for k in range(n):
        pos = (n - k) % n
        output.append(str(right_rotations[pos]))
    
    print('\n'.join(output))

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