結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
![]() |
提出日時 | 2021-03-19 03:22:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 119 ms / 2,500 ms |
コード長 | 1,070 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 81,280 KB |
最終ジャッジ日時 | 2024-11-17 10:43:30 |
合計ジャッジ時間 | 1,971 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
# coding: utf-8# Your code here!"""Binary indexed tree0-indexed, 関数は閉区間0からの区間加算、1点更新"""class BIT: #0-indexeddef __init__(self, n):self.tree = [0]*(n+1)self.tree[0] = None# self.element = [0]*(n+1)def sum(self, i): #a_0 + ... + a_{i} #閉区間s = 0; i += 1while i > 0:s += self.tree[i]i -= i & -ireturn sdef range(self,l,r): #a_l + ... + a_r 閉区間return sum(r) - sum(l-1)def add(self, i, x):i += 1while i <= n:self.tree[i] += xi += i & -i# self.element[i] += x#def get(self,i): return element[i]###########################################import syssys.setrecursionlimit(10**6)readline = sys.stdin.readline #文字列入力のときは注意n,*a = map(int,open(0).read().split())sA = sorted(a)b = BIT(n)from bisect import *ans = 0for i,ai in enumerate(a):j = bisect_left(sA, ai)ans += i - b.sum(j)b.add(j,1)print(ans)