結果

問題 No.696 square1001 and Permutation 5
ユーザー ardggyardggy
提出日時 2021-05-23 04:40:04
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
MLE  
実行時間 -
コード長 1,412 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 818,200 KB
最終ジャッジ日時 2024-10-11 04:16:38
合計ジャッジ時間 3,692 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0