結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
|
提出日時 | 2018-06-10 04:09:42 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 916 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,516 KB |
実行使用メモリ | 274,220 KB |
最終ジャッジ日時 | 2024-06-30 13:09:49 |
合計ジャッジ時間 | 9,709 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 MLE * 3 |
ソースコード
from sys import stdinfrom bisect import bisect, bisect_leftclass BIT:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def add(self, i, x):while i <= self.size:self.tree[i] += xi += i & -idef sum(self, i):ret = 0while i > 0:ret += self.tree[i]i -= i & -ireturn retdef main():N = int(input())A = list(map(int, stdin.read().splitlines()))if N == 1:print(0)returncnt = 0ans = []apnd = ans.appendbit = BIT(N)a = sorted(set(A))for i, v in enumerate(A):x = bisect(a, v)cnt += i - bit.sum(x)bit.add(x, 1)apnd(cnt)num = sorted(A)for i in range(N - 1):cnt -= bisect_left(num, A[i])cnt += N - bisect(num, A[i])apnd(cnt)print(*ans, sep='\n')main()