結果
| 問題 |
No.1282 Display Elements
|
| コンテスト | |
| ユーザー |
 neterukun
|
| 提出日時 | 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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 24 |
ソースコード
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)