結果
| 問題 | No.1115 二つの数列 / Two Sequences |
| コンテスト | |
| ユーザー |
 ronpoo
|
| 提出日時 | 2023-09-04 14:08:54 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 394 ms / 2,000 ms |
| コード長 | 5,253 bytes |
| コンパイル時間 | 901 ms |
| コンパイル使用メモリ | 82,272 KB |
| 実行使用メモリ | 104,220 KB |
| 最終ジャッジ日時 | 2024-06-22 12:32:05 |
| 合計ジャッジ時間 | 9,175 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 35 |
ソースコード
class BinaryTrie:
def __init__(self, bit_depth):
self.root = [None, None, 0] # [0-child, 1-child, count]
self.bit_start = 1 << (bit_depth - 1)
def insert(self, x):
"""xを格納"""
b = self.bit_start
node = self.root
node[2] += 1
# print(self.root)
while b:
i = bool(x & b)
if node[i] is None:
node[i] = [None, None, 1]
else:
node[i][2] += 1
node = node[i]
b >>= 1
def pop_min(self, mask=0):
"""xor_mask適用後の最小値を取得し、木からは削除"""
b = self.bit_start
node = self.root
m = mask
node[2] -= 1
ret2 = 0
while b:
i = bool(m & b)
ret2 = ret2 << 1
if node[i] is None:
i ^= 1
ret2 += 1
if node[i][2] > 1:
node[i][2] -= 1
node = node[i]
else:
tmp = node[i]
node[i] = None
node = tmp
b >>= 1
return ret2
def get_min(self, mask=0):
"""xor_mask適用後の最小値を取得"""
b = self.bit_start
node = self.root
m = mask
ret2 = 0
while b:
i = bool(m & b)
ret2 = ret2 << 1
if node[i] is None:
i ^= 1
ret2 += 1
node = node[i]
b >>= 1
return ret2
def get_kth_min(self, k=1):
"""k番目に小さい値を取得"""
b = self.bit_start
node = self.root
ret2 = 0
while b:
# print(b)
ret2 = ret2 << 1
b >>= 1
if node[0] is None:
node = node[1]
ret2 += 1
continue
if node[1] is None:
node = node[0]
continue
if k <= node[0][2]:
node = node[0]
continue
else:
k -= node[0][2]
node = node[1]
ret2 += 1
continue
return ret2
def erase(self, x):
"""xを削除"""
b = self.bit_start
node = self.root
node[2] -= 1
# print(self.root)
while b:
i = bool(x & b)
if node[i][2] > 1:
node[i][2] -= 1
node = node[i]
else:
tmp = node[i]
node[i] = None
node = tmp
b >>= 1
def lower_bound(self, bound=0):
"""boundより大きい値での最小値を取得。存在しない場合はNoneを返す。"""
ans = self.get_kth_min(self.less_x(bound+1)+1)
if ans > bound:
return ans
def upper_bound(self, bound=0):
"""boundより小さい値での最大値を取得。存在しない場合はNoneを返す。"""
ans = self.get_kth_min(self.less_x(bound))
if ans < bound:
return ans
def merge(self, trie):
"""2つのbinatytrie木を合成"""
def merges(x, y):
if (not x):
return y
if (not y):
return x
return [merges(x[0], y[0]), merges(x[1], y[1]), x[2]+y[2]]
self.root = merges(self.root, trie.root)
def less_x(self, x):
"""xより小さい値の数を出力"""
if x < 0:
return 0
b = self.bit_start
node = self.root
ans = 0
# print(self.root)
while b:
i = bool(x & b)
if node[i] is None:
if i == 1:
ans += node[0][2]
return ans
if i == 1:
if node[0] is not None:
ans += node[0][2]
node = node[i]
b >>= 1
return ans
def less_x_mask(self, x, mask=0):
"""xormask適用後,xより小さい値の数を出力"""
if x < 0:
return 0
b = self.bit_start
node = self.root
ans = 0
m = mask
# print(self.root)
while b:
i = bool(x & b)
mm = bool(m & b)
imm = i ^ mm
if node[imm] is None:
if i == 1:
ans += node[imm ^ 1][2]
return ans
if i == 1:
if node[imm ^ 1] is not None:
ans += node[imm ^ 1][2]
node = node[imm]
b >>= 1
return ans
def is_exist(self, x):
"""xが存在するか判定"""
b = self.bit_start
node = self.root
node[2] -= 1
# print(self.root)
while b:
i = bool(x & b)
if node[i] is None:
return False
node = node[i]
b >>= 1
return True
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [-1] * n
for i in range(n):
c[b[i]-1] = i
bt=BinaryTrie(20)
ans = 0
for i in range(n-1, -1, -1):
v = c[a[i]-1]
ans += bt.less_x(v)
bt.insert(v)
print(ans)