結果

問題 No.696 square1001 and Permutation 5
コンテスト
ユーザー ardggy
提出日時 2021-05-23 04:39:42
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,411 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 848,552 KB
最終ジャッジ日時 2024-10-11 04:16:20
合計ジャッジ時間 4,812 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1000000)
def debug(*args, **kwd):
    import os
    if os.getenv('DEBUG'): print(*args, **kwd, file=sys.stderr)

def input():
    return sys.stdin.readline()[:-1]

def int0(s: str) -> int:
    return int(s) - 1

class Fenwick:
    __slots__ = ["size", "tree"]

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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def main(_=0):
    N = int(input())
    P = [int(x) for x in input().split()]

    fact = [0] * (N+1); fact[1] = 1
    for i in range(2, N+1):
        fact[i] = fact[i-1] * i

    fenwick = Fenwick(N)
    k, n = 1, N
    for a in P:
        x = a - fenwick.sum(a) - 1
        fenwick.add(a-1, 1)
        k += x * fact[n-1]
        n -= 1

    print(k)

def as_input(s: str) -> None:
    import io
    global input
    f = io.StringIO(s)
    input = lambda: f.readline().rstrip()
    return None

sample1 = """3
2 3 1
"""
sample2 = """5
3 1 5 4 2
"""
sample3 = """5
1 4 3 2 5
"""
def test():
    """
    >>> main(as_input(sample1))
    4
    >>> main(as_input(sample2))
    54
    >>> main(as_input(sample3))
    15
    """
    pass

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