結果

問題 No.1838 Modulo Straight
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:13:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,273 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 207,104 KB
最終ジャッジ日時 2025-06-12 16:13:30
合計ジャッジ時間 13,261 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 17 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    if M == 1:
        print(0)
        return

    x = A[0]
    T_x = [(x + i) % M for i in range(M * K)]

    pos_in_T = {}
    for idx, val in enumerate(T_x):
        if val not in pos_in_T:
            pos_in_T[val] = []
        pos_in_T[val].append(idx)

    P = []
    for a in A:
        q = pos_in_T[a].pop(0)
        P.append(q)

    size = M * K
    max_val = size

    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (size + 1)

        def update(self, index, delta=1):
            while index <= self.size:
                self.tree[index] += delta
                index += index & -index

        def query(self, index):
            res = 0
            while index > 0:
                res += self.tree[index]
                index -= index & -index
            return res

    ft = FenwickTree(size)
    inversions = 0
    for i in reversed(range(len(P))):
        inversions += ft.query(P[i])
        ft.update(P[i] + 1)

    print(inversions)

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