結果
| 問題 | No.2248 max(C)-min(C) |
| ユーザー |
 もちふわゆるゆる
|
| 提出日時 | 2023-03-18 13:10:38 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,685 bytes |
| コンパイル時間 | 318 ms |
| コンパイル使用メモリ | 82,308 KB |
| 実行使用メモリ | 274,520 KB |
| 最終ジャッジ日時 | 2024-09-18 13:16:41 |
| 合計ジャッジ時間 | 57,673 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 57 ms
67,456 KB |
| testcase_01 | AC | 63 ms
67,072 KB |
| testcase_02 | AC | 67 ms
67,456 KB |
| testcase_03 | AC | 71 ms
70,784 KB |
| testcase_04 | AC | 70 ms
69,888 KB |
| testcase_05 | AC | 64 ms
68,608 KB |
| testcase_06 | AC | 75 ms
74,752 KB |
| testcase_07 | AC | 85 ms
78,792 KB |
| testcase_08 | AC | 81 ms
79,232 KB |
| testcase_09 | AC | 76 ms
78,792 KB |
| testcase_10 | AC | 62 ms
68,352 KB |
| testcase_11 | AC | 85 ms
78,848 KB |
| testcase_12 | AC | 68 ms
70,656 KB |
| testcase_13 | AC | 68 ms
73,984 KB |
| testcase_14 | AC | 79 ms
78,464 KB |
| testcase_15 | AC | 78 ms
78,592 KB |
| testcase_16 | AC | 58 ms
69,888 KB |
| testcase_17 | AC | 76 ms
78,464 KB |
| testcase_18 | AC | 1,168 ms
161,428 KB |
| testcase_19 | AC | 159 ms
85,632 KB |
| testcase_20 | AC | 1,379 ms
180,632 KB |
| testcase_21 | AC | 1,271 ms
178,020 KB |
| testcase_22 | AC | 856 ms
139,900 KB |
| testcase_23 | AC | 527 ms
115,212 KB |
| testcase_24 | AC | 226 ms
92,416 KB |
| testcase_25 | AC | 1,222 ms
179,124 KB |
| testcase_26 | AC | 1,049 ms
154,628 KB |
| testcase_27 | AC | 1,167 ms
173,032 KB |
| testcase_28 | AC | 141 ms
82,816 KB |
| testcase_29 | AC | 1,049 ms
152,992 KB |
| testcase_30 | AC | 399 ms
104,744 KB |
| testcase_31 | AC | 1,428 ms
178,988 KB |
| testcase_32 | AC | 249 ms
92,032 KB |
| testcase_33 | AC | 389 ms
104,480 KB |
| testcase_34 | AC | 1,392 ms
184,892 KB |
| testcase_35 | AC | 1,419 ms
182,940 KB |
| testcase_36 | AC | 1,370 ms
178,988 KB |
| testcase_37 | AC | 662 ms
128,640 KB |
| testcase_38 | AC | 2,346 ms
274,520 KB |
| testcase_39 | AC | 2,621 ms
271,956 KB |
| testcase_40 | AC | 2,902 ms
273,328 KB |
| testcase_41 | AC | 2,003 ms
247,236 KB |
| testcase_42 | AC | 2,470 ms
274,488 KB |
| testcase_43 | AC | 2,042 ms
246,556 KB |
| testcase_44 | AC | 2,419 ms
273,652 KB |
| testcase_45 | AC | 1,742 ms
222,724 KB |
| testcase_46 | AC | 907 ms
131,712 KB |
| testcase_47 | AC | 2,446 ms
274,360 KB |
| testcase_48 | AC | 1,501 ms
271,864 KB |
| testcase_49 | AC | 2,871 ms
272,468 KB |
| testcase_50 | TLE | - |
| testcase_51 | AC | 2,842 ms
272,448 KB |
| testcase_52 | AC | 2,817 ms
273,196 KB |
| testcase_53 | AC | 434 ms
97,512 KB |
ソースコード
import sys, math
input = lambda: sys.stdin.readline()[:-1]
def MI(): return map(int, input().split())
inf = 10**18
# 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
"""
SortedSet: 平衡二分探索木
ソート済み列をいくつかのバケット (list) に分割して管理します。このとき、(バケットの個数) : (バケット内の個数) = 1 : 50 くらいにします。(list の insert / pop の定数倍が軽く、バケット再構築の定数倍が重いため)
あるバケットが空になったり、多すぎたりしたら、1 度まとめて、均等にバケットに分割します。
基本的に、全ての操作が O(√N) で、(どのバケットか探す時間) < (バケットの中を探す時間) < (バケットへの挿入・削除) の順に重くなります。
SortedSet(a=[])
iterable から SortedSet を作ります。重複がなく、かつソートされていれば O(N) 、そうでなければ O(N log N) です。
s.a
SortedSet の中身です。list の list になっていて、中には要素が昇順に並んでいます。各バケットには要素が存在することが保証されます。
len(s)
O(1)
x in s / x not in s
O(√N)
s.add(x)
x が s に含まれていなければ x を追加し、True を返します。O(√N) amotized / O(N) worst
s.discard(x)
x が s に含まれていれば x を削除し、True を返します。O(√N) amotized / O(N) worst
s.lt(x) / s.le(x) / s.gt(x) / s.ge(x)
x より小さい / 以下 / より大きい / 以上で 最小 / 最大 の要素を返します。存在しなければ None をを返します。O(√N)
s[x]
下から x 番目 / 上から ~x 番目 の要素を返します。存在しない場合は IndexError を返します。O(√N) (定数倍が小さい)
sort済みだからs[-1], s[0]のように取得可能
s.index(x)
x より小さい要素の数を返します。x が s に含まれている場合は list(s).index(x) に相当します。O(√N) (定数倍が小さい)
indexとしてはxより小さい要素のindex+1が返ってくる
s.index_right(x)
x 以下の要素の数を返します。O(√N) (定数倍が小さい)
indexとしてはx以下の要素のindex+1が返ってくる
SortedMultiset
SortedSet の多重集合版です。同じ要素を複数入れることができます。SortedSet からの変更点は以下の通りです。
s.add(x)
x が s に含まれているかどうかに関わらず x を追加します。何も返しません。O(√N) amotized / O(N) worst
s.discard(x)
x が s に含まれていれば x を 1 個 削除し、True を返します。O(√N) amotized / O(N) worst
(C++ の std::multiset::erase には x を全て削除してしまうという罠があります。)
s.count(x)
s に含まれる x の個数を返します。O(√N) (定数倍が小さい)
"""
n, = MI()
a = list(MI())
b = list(MI())
ab = [(a[i]+b[i])//2 for i in range(n)]
events = []
for i in range(n):
if a[i] > b[i]:
a[i], b[i] = b[i], a[i]
events.append(a[i]*10**20 + i*10**10 + 0)
events.append(ab[i]*10**20 + i*10**10 + 1)
events.append(b[i]*10**20 + i*10**10 + 2)
events.sort()
sm = SortedMultiset(a)
ans = inf
for e in events:
l = e // 10**20
i = (e // 10**10) % 10**10
t = e % 10**10
r = sm.le(inf)
ans = min(ans, r-l)
if t==0:
sm.discard(l)
sm.add(ab[i])
elif t==1:
sm.discard(l)
sm.add(b[i])
else:
break
print(ans)