結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー ronpooronpoo
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
77,332 KB
testcase_01 AC 39 ms
53,860 KB
testcase_02 AC 41 ms
54,160 KB
testcase_03 AC 312 ms
100,252 KB
testcase_04 AC 355 ms
103,720 KB
testcase_05 AC 320 ms
100,232 KB
testcase_06 AC 302 ms
97,200 KB
testcase_07 AC 368 ms
103,576 KB
testcase_08 AC 79 ms
76,508 KB
testcase_09 AC 154 ms
91,624 KB
testcase_10 AC 221 ms
104,220 KB
testcase_11 AC 40 ms
54,068 KB
testcase_12 AC 394 ms
103,808 KB
testcase_13 AC 387 ms
103,792 KB
testcase_14 AC 382 ms
104,212 KB
testcase_15 AC 40 ms
54,048 KB
testcase_16 AC 39 ms
54,436 KB
testcase_17 AC 40 ms
54,160 KB
testcase_18 AC 44 ms
59,596 KB
testcase_19 AC 49 ms
62,248 KB
testcase_20 AC 40 ms
53,928 KB
testcase_21 AC 39 ms
53,716 KB
testcase_22 AC 40 ms
53,764 KB
testcase_23 AC 92 ms
77,372 KB
testcase_24 AC 162 ms
85,064 KB
testcase_25 AC 283 ms
97,012 KB
testcase_26 AC 112 ms
79,988 KB
testcase_27 AC 189 ms
86,648 KB
testcase_28 AC 244 ms
91,468 KB
testcase_29 AC 309 ms
97,236 KB
testcase_30 AC 364 ms
103,348 KB
testcase_31 AC 130 ms
81,780 KB
testcase_32 AC 108 ms
79,264 KB
testcase_33 AC 200 ms
100,288 KB
testcase_34 AC 41 ms
54,132 KB
testcase_35 AC 39 ms
53,384 KB
testcase_36 AC 39 ms
53,336 KB
testcase_37 AC 40 ms
54,356 KB
testcase_38 AC 38 ms
52,940 KB
testcase_39 AC 40 ms
53,632 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0