結果
問題 | No.696 square1001 and Permutation 5 |
ユーザー |
|
提出日時 | 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 |
ソースコード
import syssys.setrecursionlimit(1000000)def debug(*args, **kwd):import osif os.getenv('DEBUG'): print(*args, **kwd, file=sys.stderr)def input():return sys.stdin.readline()[:-1]def int0(s: str) -> int:return int(s) - 1class Fenwick:__slots__ = ["size", "tree"]def __init__(self, size):self.size = sizeself.tree = [0] * (size + 1)def sum(self, i):s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef add(self, i, x):i += 1while i <= self.size:self.tree[i] += xi += i & -idef main(_=0):N = int(input())P = [int(x) for x in input().split()]fact = [0] * (N+1); fact[1] = 1for i in range(2, N+1):fact[i] = fact[i-1] * ifenwick = Fenwick(N)k, n = 1, Nfor a in P:x = a - fenwick.sum(a) - 1fenwick.add(a-1, 1)k += x * fact[n-1]n -= 1print(k)def as_input(s: str) -> None:import ioglobal inputf = io.StringIO(s)input = lambda: f.readline().rstrip()return Nonesample1 = """32 3 1"""sample2 = """53 1 5 4 2"""sample3 = """51 4 3 2 5"""def test():""">>> main(as_input(sample1))4>>> main(as_input(sample2))54>>> main(as_input(sample3))15"""passif __name__ == '__main__':main()