結果

問題 No.2248 max(C)-min(C)
ユーザー shobonvipshobonvip
提出日時 2023-03-17 21:43:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,612 ms / 3,000 ms
コード長 4,165 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 263,712 KB
最終ジャッジ日時 2024-09-18 10:32:12
合計ジャッジ時間 48,206 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
67,072 KB
testcase_01 AC 72 ms
67,456 KB
testcase_02 AC 63 ms
66,816 KB
testcase_03 AC 148 ms
79,576 KB
testcase_04 AC 139 ms
79,744 KB
testcase_05 AC 109 ms
78,464 KB
testcase_06 AC 200 ms
80,300 KB
testcase_07 AC 161 ms
79,360 KB
testcase_08 AC 160 ms
79,616 KB
testcase_09 AC 157 ms
80,000 KB
testcase_10 AC 105 ms
78,296 KB
testcase_11 AC 177 ms
79,944 KB
testcase_12 AC 147 ms
79,232 KB
testcase_13 AC 157 ms
79,604 KB
testcase_14 AC 177 ms
79,692 KB
testcase_15 AC 170 ms
79,616 KB
testcase_16 AC 124 ms
79,512 KB
testcase_17 AC 170 ms
79,480 KB
testcase_18 AC 1,357 ms
154,780 KB
testcase_19 AC 313 ms
87,680 KB
testcase_20 AC 1,487 ms
193,848 KB
testcase_21 AC 1,466 ms
184,928 KB
testcase_22 AC 1,050 ms
163,924 KB
testcase_23 AC 689 ms
133,064 KB
testcase_24 AC 416 ms
94,620 KB
testcase_25 AC 1,442 ms
177,788 KB
testcase_26 AC 1,227 ms
147,264 KB
testcase_27 AC 1,386 ms
174,916 KB
testcase_28 AC 289 ms
85,376 KB
testcase_29 AC 1,261 ms
150,724 KB
testcase_30 AC 724 ms
119,600 KB
testcase_31 AC 1,554 ms
194,048 KB
testcase_32 AC 462 ms
96,640 KB
testcase_33 AC 646 ms
114,212 KB
testcase_34 AC 1,547 ms
194,104 KB
testcase_35 AC 1,565 ms
193,852 KB
testcase_36 AC 1,612 ms
194,100 KB
testcase_37 AC 877 ms
146,736 KB
testcase_38 AC 1,555 ms
182,944 KB
testcase_39 AC 1,553 ms
183,124 KB
testcase_40 AC 1,562 ms
187,656 KB
testcase_41 AC 1,328 ms
162,024 KB
testcase_42 AC 1,552 ms
183,704 KB
testcase_43 AC 1,362 ms
168,832 KB
testcase_44 AC 1,579 ms
188,904 KB
testcase_45 AC 1,171 ms
180,612 KB
testcase_46 AC 669 ms
127,952 KB
testcase_47 AC 1,551 ms
180,528 KB
testcase_48 AC 1,507 ms
263,712 KB
testcase_49 AC 1,525 ms
224,408 KB
testcase_50 AC 1,430 ms
224,432 KB
testcase_51 AC 1,433 ms
222,504 KB
testcase_52 AC 1,549 ms
221,944 KB
testcase_53 AC 376 ms
93,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List

T = TypeVar('T')


class SortedMultiset(Generic[T]):
	BUCKET_RATIO = 50
	REBUILD_RATIO = 170
	
	def _build(self, a=None) -> None:
		"Evenly divide `a` into buckets."
		if a is None: a = list(self)
		size = self.size = len(a)
		bucket_size = int(math.ceil(math.sqrt(size/self.BUCKET_RATIO)))
		self.a = [a[size*i//bucket_size: size*(i+1)//bucket_size] for i in range(bucket_size)]
	
	def __init__(self, a: Iterable[T] = []) -> None:
		"Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
		a = list(a)
		if not all(a[i] <= a[i+1] for i in range(len(a)-1)):
			a = sorted(a)
		self._build(a)
	
	def __iter__(self) -> Iterator[T]:
		for i in self.a:
			for j in i: yield j
	
	def __reversed__(self) -> Iterator[T]:
		for i in reversed(self.a):
			for j in reversed(i): yield j
	
	def __len__(self) -> int:
		return self.size
	
	def __repr__(self) -> str:
		return "SortedMultiset"+str(self.a)
	
	def __str__(self) -> str:
		s = str(list(self))
		return "{"+s[1: len(s)-1]+"}"
	
	def _find_bucket(self, x: T) -> List[T]:
		"Find the bucket which should contain x. self must not be empty."
		for a in self.a:
			if x <= a[-1]: return a
		return a
	
	def __contains__(self, x: T) -> bool:
		if self.size == 0: return False
		a = self._find_bucket(x)
		i = bisect_left(a, x)
		return i != len(a) and a[i] == x
	
	def count(self, x: T) -> int:
		"Count the number of x."
		return self.index_right(x)-self.index(x)
	
	def add(self, x: T) -> None:
		"Add an element. / O(√N)"
		if self.size == 0:
			self.a = [[x]]
			self.size = 1
			return
		a = self._find_bucket(x)
		insort(a, x)
		self.size += 1
		if len(a) > len(self.a)*self.REBUILD_RATIO:
			self._build()
	
	def discard(self, x: T) -> bool:
		"Remove an element and return True if removed. / O(√N)"
		if self.size == 0: return False
		a = self._find_bucket(x)
		i = bisect_left(a, x)
		if i == len(a) or a[i] != x: return False
		a.pop(i)
		self.size -= 1
		if len(a) == 0: self._build()
		return True
	
	def lt(self, x: T) -> Union[T, None]:
		"Find the largest element < x, or None if it doesn't exist."
		for a in reversed(self.a):
			if a[0] < x:
				return a[bisect_left(a, x)-1]
	
	def le(self, x: T) -> Union[T, None]:
		"Find the largest element <= x, or None if it doesn't exist."
		for a in reversed(self.a):
			if a[0] <= x:
				return a[bisect_right(a, x)-1]
	
	def gt(self, x: T) -> Union[T, None]:
		"Find the smallest element > x, or None if it doesn't exist."
		for a in self.a:
			if a[-1] > x:
				return a[bisect_right(a, x)]
	
	def ge(self, x: T) -> Union[T, None]:
		"Find the smallest element >= x, or None if it doesn't exist."
		for a in self.a:
			if a[-1] >= x:
				return a[bisect_left(a, x)]
	
	def __getitem__(self, x: int) -> T:
		"Return the x-th element, or IndexError if it doesn't exist."
		if x < 0: x += self.size
		if x < 0: raise IndexError
		for a in self.a:
			if x < len(a): return a[x]
			x -= len(a)
		raise IndexError
	
	def index(self, x: T) -> int:
		"Count the number of elements < x."
		ans = 0
		for a in self.a:
			if a[-1] >= x:
				return ans+bisect_left(a, x)
			ans += len(a)
		return ans
	
	def index_right(self, x: T) -> int:
		"Count the number of elements <= x."
		ans = 0
		for a in self.a:
			if a[-1] > x:
				return ans+bisect_right(a, x)
			ans += len(a)
		return ans


n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
for i in range(n):
	if a[i] > b[i]: a[i], b[i] = b[i], a[i]

s = SortedMultiset(a)
event = []
# 0 ... add
# 1 ... delete
for i in range(n):
	t = (a[i] + b[i]) // 2
	event.append((t << 31) + (1 << 30) + a[i])
	event.append((t << 31) + t)
	event.append((b[i] << 31) + (1 << 30) + t)
	event.append((b[i] << 31) + b[i])



event.sort()
mask = (1 << 30) - 1
ans = s.lt(10 ** 12) - s.gt(-1)
for i in event:
	typ = (i >> 30) & 1
	targ = i & mask
	if typ == 0:
		s.add(targ)
	else:
		s.discard(targ)
	v = s.lt(10 ** 12) - s.gt(-1)
	ans = min(ans, v)
	#print(v)
	
print(ans)
0