結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
|
提出日時 | 2022-03-08 13:26:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 960 bytes |
コンパイル時間 | 329 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 105,728 KB |
最終ジャッジ日時 | 2024-07-23 12:57:08 |
合計ジャッジ時間 | 4,596 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
class BIT:def __init__(self, n):self.size = nself.tree = [0]*(n+1)def build(self, list):self.tree[1:] = list.copy()for i in range(self.size+1):j = i + (i & (-i))if j < self.size+1:self.tree[j] += self.tree[i]def sum(self, i):# [0, i) の要素の総和を返すs = 0while i>0:s += self.tree[i]i -= i & -ireturn s# 0 index を 1 index に変更 転倒数を求めるなら1を足していくdef add(self, i, x):i += 1while i <= self.size:self.tree[i] += xi += i & -in = int(input())A = list(map(int,input().split()))B = list(map(int,input().split()))id = [-1]*(n+1)for i,b in enumerate(B):id[b] = iiA = [id[a] for a in A]bit = BIT(n+5)ans = 0for i,a in enumerate(iA):s = bit.sum(a)ans += i-sbit.add(a,1)print(ans)