結果

問題 No.694 square1001 and Permutation 3
ユーザー lam6er
提出日時 2025-04-16 00:04:38
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,082 bytes
コンパイル時間 472 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 257,940 KB
最終ジャッジ日時 2025-04-16 00:06:41
合計ジャッジ時間 7,105 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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]))
    
    # Compute count_less and count_greater for each element
    sorted_A = sorted(A)
    count_less = [0] * n
    count_greater = [0] * n
    for i in range(n):
        x = A[i]
        l = bisect.bisect_left(sorted_A, x)
        r = bisect.bisect_right(sorted_A, x)
        count_less[i] = l
        count_equal = r - l
        count_greater[i] = n - (l + count_equal)
    
    # Compress the array for Fenwick Tree
    unique = []
    prev = None
    for x in sorted_A:
        if x != prev:
            unique.append(x)
            prev = x
    rank_dict = {v: i for i, v in enumerate(unique)}
    compressed = [rank_dict[x] for x in A]
    max_rank = len(unique) - 1
    
    # Fenwick Tree implementation
    class FenwickTree:
        def __init__(self, size):
            self.n = size
            self.tree = [0] * (self.n + 2)  # 1-based indexing
        
        def update(self, idx, delta=1):
            # Convert to 1-based index
            idx += 1
            while idx <= self.n + 1:
                self.tree[idx] += delta
                idx += idx & -idx
        
        def query(self, idx):
            # Sum from 1-based index 1 to idx+1 (original 0 to idx)
            res = 0
            idx += 1  # convert to 1-based
            while idx > 0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res
    
    # Compute initial inversion count
    ft = FenwickTree(max_rank)
    inv_count = 0
    for i in reversed(range(n)):
        r = compressed[i]
        cnt = ft.query(r - 1)
        inv_count += cnt
        ft.update(r)
    
    # Compute results for all rotations
    res = [inv_count]
    current = inv_count
    for i in range(n - 1):
        current = current - count_less[i] + count_greater[i]
        res.append(current)
    
    # Output the results
    sys.stdout.write('\n'.join(map(str, res)) + '\n')

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