結果

問題 No.694 square1001 and Permutation 3
ユーザー lam6er
提出日時 2025-04-16 00:04:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,229 ms / 3,000 ms
コード長 2,252 bytes
コンパイル時間 396 ms
コンパイル使用メモリ 82,484 KB
実行使用メモリ 201,976 KB
最終ジャッジ日時 2025-04-16 00:06:34
合計ジャッジ時間 13,140 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing
    
    def update(self, idx, delta=1):
        while idx <= self.n:
            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

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr + n]))
    ptr += n

    # Coordinate compression
    sorted_A = sorted(A)
    unique = []
    prev = None
    for x in sorted_A:
        if x != prev:
            unique.append(x)
            prev = x
    m = len(unique)
    
    def get_rank(x):
        return bisect.bisect_left(unique, x) + 1  # 1-based
    
    # Compute initial inversion count
    fenwick = FenwickTree(m)
    initial = 0
    for i in reversed(range(n)):
        x = A[i]
        r = get_rank(x)
        initial += fenwick.query(r - 1)
        fenwick.update(r)
    
    # Compute left_less and left_greater
    fenwick = FenwickTree(m)
    left_less = [0] * n
    left_greater = [0] * n
    for i in range(n):
        x = A[i]
        r = get_rank(x)
        left_less[i] = fenwick.query(r - 1)
        left_greater[i] = fenwick.query(m) - fenwick.query(r)
        fenwick.update(r)
    
    # Compute right_less and right_greater
    fenwick = FenwickTree(m)
    right_less = [0] * n
    right_greater = [0] * n
    for i in reversed(range(n)):
        x = A[i]
        r = get_rank(x)
        right_less[i] = fenwick.query(r - 1)
        right_greater[i] = fenwick.query(m) - fenwick.query(r)
        fenwick.update(r)
    
    # Compute delta for each index
    delta = [0] * n
    for i in range(n):
        d = (right_greater[i] + left_greater[i]) - (right_less[i] + left_less[i])
        delta[i] = d
    
    # Compute the answer array
    ans = [0] * n
    current = initial
    for k in range(n):
        ans[k] = current
        if k < n - 1:
            current += delta[k]
    
    # Print each line of ans
    print('\n'.join(map(str, ans)))

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