結果
| 問題 | No.1115 二つの数列 / Two Sequences |
| ユーザー |
 ronpoo
|
| 提出日時 | 2023-09-04 14:08:54 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 431 ms / 2,000 ms |
| コード長 | 5,253 bytes |
| コンパイル時間 | 642 ms |
| コンパイル使用メモリ | 87,088 KB |
| 実行使用メモリ | 106,652 KB |
| 最終ジャッジ日時 | 2023-09-04 14:09:08 |
| 合計ジャッジ時間 | 12,397 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 120 ms
78,136 KB |
| testcase_01 | AC | 75 ms
71,328 KB |
| testcase_02 | AC | 76 ms
71,448 KB |
| testcase_03 | AC | 375 ms
100,304 KB |
| testcase_04 | AC | 415 ms
106,052 KB |
| testcase_05 | AC | 360 ms
100,768 KB |
| testcase_06 | AC | 332 ms
98,116 KB |
| testcase_07 | AC | 416 ms
106,020 KB |
| testcase_08 | AC | 111 ms
77,868 KB |
| testcase_09 | AC | 184 ms
92,672 KB |
| testcase_10 | AC | 248 ms
103,308 KB |
| testcase_11 | AC | 74 ms
71,240 KB |
| testcase_12 | AC | 431 ms
106,652 KB |
| testcase_13 | AC | 404 ms
106,464 KB |
| testcase_14 | AC | 405 ms
106,096 KB |
| testcase_15 | AC | 80 ms
71,224 KB |
| testcase_16 | AC | 73 ms
71,232 KB |
| testcase_17 | AC | 73 ms
71,252 KB |
| testcase_18 | AC | 78 ms
75,080 KB |
| testcase_19 | AC | 84 ms
75,936 KB |
| testcase_20 | AC | 76 ms
71,412 KB |
| testcase_21 | AC | 75 ms
71,016 KB |
| testcase_22 | AC | 77 ms
71,200 KB |
| testcase_23 | AC | 119 ms
77,972 KB |
| testcase_24 | AC | 186 ms
86,040 KB |
| testcase_25 | AC | 333 ms
97,748 KB |
| testcase_26 | AC | 135 ms
80,920 KB |
| testcase_27 | AC | 212 ms
87,508 KB |
| testcase_28 | AC | 254 ms
92,648 KB |
| testcase_29 | AC | 350 ms
97,868 KB |
| testcase_30 | AC | 376 ms
105,332 KB |
| testcase_31 | AC | 156 ms
82,852 KB |
| testcase_32 | AC | 136 ms
80,092 KB |
| testcase_33 | AC | 223 ms
100,556 KB |
| testcase_34 | AC | 72 ms
71,396 KB |
| testcase_35 | AC | 79 ms
71,084 KB |
| testcase_36 | AC | 74 ms
71,344 KB |
| testcase_37 | AC | 73 ms
71,360 KB |
| testcase_38 | AC | 74 ms
71,128 KB |
| testcase_39 | AC | 72 ms
71,484 KB |
ソースコード
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)