結果
問題 | No.2248 max(C)-min(C) |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.pyimport mathfrom bisect import bisect_left, bisect_right, insortfrom typing import Generic, Iterable, Iterator, TypeVar, Union, ListT = TypeVar('T')class SortedMultiset(Generic[T]):BUCKET_RATIO = 50REBUILD_RATIO = 170def _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 jdef __reversed__(self) -> Iterator[T]:for i in reversed(self.a):for j in reversed(i): yield jdef __len__(self) -> int:return self.sizedef __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 areturn adef __contains__(self, x: T) -> bool:if self.size == 0: return Falsea = self._find_bucket(x)i = bisect_left(a, x)return i != len(a) and a[i] == xdef 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 = 1returna = self._find_bucket(x)insort(a, x)self.size += 1if 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 Falsea = self._find_bucket(x)i = bisect_left(a, x)if i == len(a) or a[i] != x: return Falsea.pop(i)self.size -= 1if len(a) == 0: self._build()return Truedef 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.sizeif x < 0: raise IndexErrorfor a in self.a:if x < len(a): return a[x]x -= len(a)raise IndexErrordef index(self, x: T) -> int:"Count the number of elements < x."ans = 0for a in self.a:if a[-1] >= x:return ans+bisect_left(a, x)ans += len(a)return ansdef index_right(self, x: T) -> int:"Count the number of elements <= x."ans = 0for a in self.a:if a[-1] > x:return ans+bisect_right(a, x)ans += len(a)return ansn = 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 ... deletefor i in range(n):t = (a[i] + b[i]) // 2event.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) - 1ans = s.lt(10 ** 12) - s.gt(-1)for i in event:typ = (i >> 30) & 1targ = i & maskif 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)