結果

問題 No.1282 Display Elements
ユーザー neterukunneterukun
提出日時 2020-11-06 21:50:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 586 ms / 2,000 ms
コード長 6,505 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 102,528 KB
最終ジャッジ日時 2024-07-22 12:41:13
合計ジャッジ時間 6,217 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
54,400 KB
testcase_01 AC 46 ms
54,784 KB
testcase_02 AC 46 ms
55,040 KB
testcase_03 AC 46 ms
54,784 KB
testcase_04 AC 46 ms
55,040 KB
testcase_05 AC 46 ms
54,656 KB
testcase_06 AC 46 ms
54,912 KB
testcase_07 AC 45 ms
54,656 KB
testcase_08 AC 46 ms
54,784 KB
testcase_09 AC 46 ms
54,784 KB
testcase_10 AC 73 ms
69,248 KB
testcase_11 AC 75 ms
70,144 KB
testcase_12 AC 49 ms
55,296 KB
testcase_13 AC 71 ms
67,200 KB
testcase_14 AC 85 ms
73,216 KB
testcase_15 AC 515 ms
102,528 KB
testcase_16 AC 346 ms
84,992 KB
testcase_17 AC 483 ms
97,280 KB
testcase_18 AC 388 ms
87,680 KB
testcase_19 AC 210 ms
100,224 KB
testcase_20 AC 220 ms
99,840 KB
testcase_21 AC 586 ms
100,180 KB
testcase_22 AC 438 ms
100,132 KB
testcase_23 AC 586 ms
99,840 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from random import random 
import sys
input = sys.stdin.buffer.readline
 
 
class TreapNode:
    """Treapのノード定義"""
    def __init__(self, val):
        self.val = val
        self.priority = random()
        self.size = 1
        self.sum_ = val
        self.parent, self.right, self.left = None, None, None
        
 
class Treap:
    """平衡二分探索木: 値の検索、挿入、削除などクエリ処理をO(logN)で実行する"""
    def __init__(self):
        self.root = None
 
    def search(self, val: int) -> bool:
        """値の検索: 集合に値valを持つノードが存在するか"""
        ptr = self.root
        while ptr is not None:
            if val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                return True
        return False
 
    def insert(self, val: int) -> bool:
        """値の挿入: 集合に値valを持つノードを挿入する"""
        if self.root is None:
            self.root = TreapNode(val)
            return True
 
        # ノードの挿入
        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    ptr.left = TreapNode(val)
                    ptr.left.parent = ptr
                    ptr = ptr.left
                    break
                ptr = ptr.left
            else:
                if ptr.right is None:
                    ptr.right = TreapNode(val)
                    ptr.right.parent = ptr
                    ptr = ptr.right
                    break
                ptr = ptr.right
 
 
        # 木の回転によってヒープ性を保つ
        if ptr.priority < 0.2:  # 木の回転をサボる
            while (ptr.parent is not None) and (ptr.parent.priority > ptr.priority):
                if ptr.parent.right == ptr:
                    self._rotate_left(ptr.parent)
                else:
                    self._rotate_right(ptr.parent)
            if ptr.parent is None:
                self.root = ptr 
            
        tmp = ptr.parent
        while tmp is not None:
            self.update(tmp)
            tmp = tmp.parent
        return True
 
    def delete(self, val: int) -> True:
        """値の削除: 集合から値valを持つノードを削除する"""
        if self.root is None:
            return False
 
        ptr = self.root   
        tmp = None
        while ptr is not None: 
            if val < ptr.val:
                ptr = ptr.left
            elif val > ptr.val:
                ptr = ptr.right
            else:
                tmp = ptr
                if (ptr.right is not None) and ptr.right.val == val:
                    ptr = ptr.right
                elif (ptr.left is not None) and ptr.left.val == val:
                    ptr = ptr.left
                else:
                    break
        ptr = tmp
        # 木の回転によって削除したいノードを葉に持っていく
        while (ptr.left is not None) or (ptr.right is not None):
            if ptr.left is None:
                self._rotate_left(ptr)
            elif ptr.right is None:
                self._rotate_right(ptr)
            elif ptr.left.priority < ptr.right.priority:
                self._rotate_right(ptr)
            else:
                self._rotate_left(ptr)
            if self.root == ptr:
                self.root = ptr.parent
 
        # ノードの削除
        if ptr.left is None and ptr.right is None:
            if ptr == self.root:
                self.root = None
            elif ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None      
 
        tmp = ptr.parent
        while tmp is not None:
            self.update(tmp)
            tmp = tmp.parent
 
        return True
 
    def _rotate_left(self, ptr):
        """木の左回転を行う"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None
        self.update(ptr)
        self.update(w)
 
    def _rotate_right(self, ptr):
        """木の右回転を行う"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None
        self.update(ptr)
        self.update(w)
 
    def update(self, ptr):
        """部分木の情報を更新する"""
        ptr.size = 1
        ptr.sum_ = ptr.val
        if ptr.left is not None:
            ptr.size += ptr.left.size
            ptr.sum_ += ptr.left.sum_
        if ptr.right is not None:
            ptr.size += ptr.right.size
            ptr.sum_ += ptr.right.sum_
            
    def get_sum(self, ind):
        ptr = self.root
        sum_ = 0
        while True:
            l_size = 0
            if ptr.left is not None:
                l_size = ptr.left.size
            if ind < l_size: 
                ptr = ptr.left
                continue
            if ind == l_size:
                sum_ += ptr.val
                if ptr.left is not None:
                    sum_ += ptr.left.sum_
                return sum_
            sum_ += ptr.val
            if ptr.left is not None:
                sum_ += ptr.left.sum_
            ptr = ptr.right
            ind -= l_size + 1

    def search_lt(self, val):
        nd = self.root
        sz = 0
        while nd is not None:
            if nd.val < val:
                if nd.left is not None:
                    sz += nd.left.size
                sz += 1
                nd = nd.right
            else: nd = nd.left
        return sz

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))


a = sorted(a)


tp = Treap()
ans = 0
for vala, valb in zip(a, b):
    tp.insert(valb)
    ans += tp.search_lt(vala)
print(ans)
0