結果
| 問題 |
No.1767 BLUE to RED
|
| コンテスト | |
| ユーザー |
 horitaka1999
|
| 提出日時 | 2021-11-27 00:55:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,875 bytes |
| コンパイル時間 | 134 ms |
| コンパイル使用メモリ | 82,296 KB |
| 実行使用メモリ | 176,772 KB |
| 最終ジャッジ日時 | 2024-06-29 19:18:53 |
| 合計ジャッジ時間 | 7,489 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 WA * 9 |
ソースコード
class BalancingTree:
def __init__(self, n):
self.N = n
self.root = self.node(1<<n, 1<<n)
def add(self, v):# v を追加（その時点で v はない前提）
v += 1
nd = self.root
while True:
if v == nd.value:
# v がすでに存在する場合に何か処理が必要ならここに書く
return 0
else:
mi, ma = min(v, nd.value), max(v, nd.value)
if mi < nd.pivot:
nd.value = ma
if nd.left:
nd = nd.left
v = mi
else:
p = nd.pivot
nd.left = self.node(mi, p - (p&-p)//2)
break
else:
nd.value = mi
if nd.right:
nd = nd.right
v = ma
else:
p = nd.pivot
nd.right = self.node(ma, p + (p&-p)//2)
break
def leftmost(self, nd):
if nd.left: return self.leftmost(nd.left)
return nd
def rightmost(self, nd):
if nd.right: return self.rightmost(nd.right)
return nd
def find_l(self, v): # vより真に小さいやつの中での最大値（なければ-1）
v += 1
nd = self.root
prev = 0
if nd.value < v: prev = nd.value
while True:
if v <= nd.value:
if nd.left:
nd = nd.left
else:
return prev - 1
else:
prev = nd.value
if nd.right:
nd = nd.right
else:
return prev - 1
def find_r(self, v): # vより真に大きいやつの中での最小値（なければRoot）
v += 1
nd = self.root
prev = 0
if nd.value > v: prev = nd.value
while True:
if v < nd.value:
prev = nd.value
if nd.left:
nd = nd.left
else:
return prev - 1
else:
if nd.right:
nd = nd.right
else:
return prev - 1
@property
def max(self):
return self.find_l((1<<self.N)-1)
@property
def min(self):
return self.find_r(-1)
def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除（なければ何もしない）
v += 1
if not nd: nd = self.root
if not prev: prev = nd
while v != nd.value:
prev = nd
if v <= nd.value:
if nd.left:
nd = nd.left
else:
#####
return
else:
if nd.right:
nd = nd.right
else:
#####
return
if (not nd.left) and (not nd.right):
if not prev.left:
prev.right = None
elif not prev.right:
prev.left = None
else:
if nd.pivot == prev.left.pivot:
prev.left = None
else:
prev.right = None
elif nd.right:
# print("type A", v)
nd.value = self.leftmost(nd.right).value
self.delete(nd.value - 1, nd.right, nd)
else:
# print("type B", v)
nd.value = self.rightmost(nd.left).value
self.delete(nd.value - 1, nd.left, nd)
def __contains__(self, v: int) -> bool:
return self.find_r(v - 1) == v
class node:
def __init__(self, v, p):
self.value = v
self.pivot = p
self.left = None
self.right = None
def debug(self):
def debug_info(nd_):
return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)
def debug_node(nd):
re = []
if nd.left:
re += debug_node(nd.left)
if nd.value: re.append(debug_info(nd))
if nd.right:
re += debug_node(nd.right)
return re
print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])
def debug_list(self):
def debug_node(nd):
re = []
if nd.left:
re += debug_node(nd.left)
if nd.value: re.append(nd.value - 1)
if nd.right:
re += debug_node(nd.right)
return re
return debug_node(self.root)[:-1]
def diff_list(List):
rev = []
for i in range(len(List)):
if i + 1 < (len(List)):
tmp = List[i+1] - List[i]
rev.append(tmp)
return rev
N,M = map(int,input().split())
from collections import defaultdict,deque
A = list(map(int,input().split()))
INF = float('inf')
A.append(0)
A.sort()
adic = defaultdict(int)
for index in range(len(A)):
adic[A[index]] = index
B = list(map(int,input().split()))
B.sort()
store = defaultdict(list)
BT = BalancingTree(32)
for a in A:
BT.add(a)
for index,b in enumerate(B):
l = BT.find_l(b)
store[adic[l]].append(b)
ans = 0
for i in range(len(A)):
if i == len(A) -1:
store[i].append(A[i])
store[i].sort()
if len(store[i]) > 1:
ans += store[i][-1] - store[i][0]
else:
store[i].append(A[i])
store[i].append(A[i+1])
store[i].sort()
if len(store[i]) > 2:
maxdis = max(diff_list(store[i]))
ans += (store[i][-1] - store[i][0]) - maxdis
print(ans)