結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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