結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
![]() |
提出日時 | 2021-05-10 05:20:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 714 bytes |
コンパイル時間 | 148 ms |
コンパイル使用メモリ | 82,280 KB |
実行使用メモリ | 104,576 KB |
最終ジャッジ日時 | 2024-09-19 09:12:53 |
合計ジャッジ時間 | 5,427 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
class BIT: #0-indexed def __init__(self, n): self.tree = [0]*(n+1) def sum(self, i): #a_0 + ... + a_{i} #閉区間 s = 0; i += 1 while i > 0: s += self.tree[i] i -= i & -i return s def range(self,l,r): #a_l + ... + a_r 閉区間 return sum(r) - sum(l-1) def add(self, i, x): i += 1 while i <= n: self.tree[i] += x i += i & -i n = int(input()) *a, = map(int,input().split()) *b, = map(int,input().split()) r = [0]*n for i in range(n): r[a[i]-1] = i for i in range(n): b[i] = r[b[i]-1] bit = BIT(n) ans = 0 for i,bi in enumerate(b): ans += i-bit.sum(bi) bit.add(bi,1) print(ans)