結果
| 問題 |
No.2812 Plus Minus Blackboard
|
| コンテスト | |
| ユーザー |
 Butterflv
|
| 提出日時 | 2024-07-19 22:54:43 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 63,865 bytes |
| コンパイル時間 | 201 ms |
| コンパイル使用メモリ | 82,332 KB |
| 実行使用メモリ | 112,120 KB |
| 最終ジャッジ日時 | 2025-04-08 23:44:08 |
| 合計ジャッジ時間 | 7,911 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 16 WA * 6 RE * 1 |
ソースコード
from __future__ import print_function
import sys
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
try:
from collections.abc import Sequence, MutableSequence
except ImportError:
from collections import Sequence, MutableSequence
from functools import wraps
from sys import hexversion
if hexversion < 0x03000000:
from itertools import imap as map # pylint: disable=redefined-builtin
from itertools import izip as zip # pylint: disable=redefined-builtin
try:
from thread import get_ident
except ImportError:
from dummy_thread import get_ident
else:
from functools import reduce
try:
from _thread import get_ident
except ImportError:
from _dummy_thread import get_ident
def recursive_repr(fillvalue='...'):
def decorating_function(user_function):
repr_running = set()
@wraps(user_function)
def wrapper(self):
key = id(self), get_ident()
if key in repr_running:
return fillvalue
repr_running.add(key)
try:
result = user_function(self)
finally:
repr_running.discard(key)
return result
return wrapper
return decorating_function
class SortedList(MutableSequence):
DEFAULT_LOAD_FACTOR = 1000
def __init__(self, iterable=None, key=None):
assert key is None
self._len = 0
self._load = self.DEFAULT_LOAD_FACTOR
self._lists = []
self._maxes = []
self._index = []
self._offset = 0
if iterable is not None:
self._update(iterable)
def __new__(cls, iterable=None, key=None):
if key is None:
return object.__new__(cls)
else:
if cls is SortedList:
return object.__new__(SortedKeyList)
else:
raise TypeError('inherit SortedKeyList for key argument')
@property
def key(self): # pylint: disable=useless-return
return None
def _reset(self, load):
values = reduce(iadd, self._lists, [])
self._clear()
self._load = load
self._update(values)
def clear(self):
self._len = 0
del self._lists[:]
del self._maxes[:]
del self._index[:]
self._offset = 0
_clear = clear
def add(self, value):
_lists = self._lists
_maxes = self._maxes
if _maxes:
pos = bisect_right(_maxes, value)
if pos == len(_maxes):
pos -= 1
_lists[pos].append(value)
_maxes[pos] = value
else:
insort(_lists[pos], value)
self._expand(pos)
else:
_lists.append([value])
_maxes.append(value)
self._len += 1
def _expand(self, pos):
_load = self._load
_lists = self._lists
_index = self._index
if len(_lists[pos]) > (_load << 1):
_maxes = self._maxes
_lists_pos = _lists[pos]
half = _lists_pos[_load:]
del _lists_pos[_load:]
_maxes[pos] = _lists_pos[-1]
_lists.insert(pos + 1, half)
_maxes.insert(pos + 1, half[-1])
del _index[:]
else:
if _index:
child = self._offset + pos
while child:
_index[child] += 1
child = (child - 1) >> 1
_index[0] += 1
def update(self, iterable):
_lists = self._lists
_maxes = self._maxes
values = sorted(iterable)
if _maxes:
if len(values) * 4 >= self._len:
_lists.append(values)
values = reduce(iadd, _lists, [])
values.sort()
self._clear()
else:
_add = self.add
for val in values:
_add(val)
return
_load = self._load
_lists.extend(values[pos:(pos + _load)]
for pos in range(0, len(values), _load))
_maxes.extend(sublist[-1] for sublist in _lists)
self._len = len(values)
del self._index[:]
_update = update
def __contains__(self, value):
_maxes = self._maxes
if not _maxes:
return False
pos = bisect_left(_maxes, value)
if pos == len(_maxes):
return False
_lists = self._lists
idx = bisect_left(_lists[pos], value)
return _lists[pos][idx] == value
def discard(self, value):
_maxes = self._maxes
if not _maxes:
return
pos = bisect_left(_maxes, value)
if pos == len(_maxes):
return
_lists = self._lists
idx = bisect_left(_lists[pos], value)
if _lists[pos][idx] == value:
self._delete(pos, idx)
def remove(self, value):
_maxes = self._maxes
if not _maxes:
raise ValueError('{0!r} not in list'.format(value))
pos = bisect_left(_maxes, value)
if pos == len(_maxes):
raise ValueError('{0!r} not in list'.format(value))
_lists = self._lists
idx = bisect_left(_lists[pos], value)
if _lists[pos][idx] == value:
self._delete(pos, idx)
else:
raise ValueError('{0!r} not in list'.format(value))
def _delete(self, pos, idx):
_lists = self._lists
_maxes = self._maxes
_index = self._index
_lists_pos = _lists[pos]
del _lists_pos[idx]
self._len -= 1
len_lists_pos = len(_lists_pos)
if len_lists_pos > (self._load >> 1):
_maxes[pos] = _lists_pos[-1]
if _index:
child = self._offset + pos
while child > 0:
_index[child] -= 1
child = (child - 1) >> 1
_index[0] -= 1
elif len(_lists) > 1:
if not pos:
pos += 1
prev = pos - 1
_lists[prev].extend(_lists[pos])
_maxes[prev] = _lists[prev][-1]
del _lists[pos]
del _maxes[pos]
del _index[:]
self._expand(prev)
elif len_lists_pos:
_maxes[pos] = _lists_pos[-1]
else:
del _lists[pos]
del _maxes[pos]
del _index[:]
def _loc(self, pos, idx):
if not pos:
return idx
_index = self._index
if not _index:
self._build_index()
total = 0
pos += self._offset
while pos:
if not pos & 1:
total += _index[pos - 1]
pos = (pos - 1) >> 1
return total + idx
def _pos(self, idx):
if idx < 0:
last_len = len(self._lists[-1])
if (-idx) <= last_len:
return len(self._lists) - 1, last_len + idx
idx += self._len
if idx < 0:
raise IndexError('list index out of range')
elif idx >= self._len:
raise IndexError('list index out of range')
if idx < len(self._lists[0]):
return 0, idx
_index = self._index
if not _index:
self._build_index()
pos = 0
child = 1
len_index = len(_index)
while child < len_index:
index_child = _index[child]
if idx < index_child:
pos = child
else:
idx -= index_child
pos = child + 1
child = (pos << 1) + 1
return (pos - self._offset, idx)
def _build_index(self):
row0 = list(map(len, self._lists))
if len(row0) == 1:
self._index[:] = row0
self._offset = 0
return
head = iter(row0)
tail = iter(head)
row1 = list(starmap(add, zip(head, tail)))
if len(row0) & 1:
row1.append(row0[-1])
if len(row1) == 1:
self._index[:] = row1 + row0
self._offset = 1
return
size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
row1.extend(repeat(0, size - len(row1)))
tree = [row0, row1]
while len(tree[-1]) > 1:
head = iter(tree[-1])
tail = iter(head)
row = list(starmap(add, zip(head, tail)))
tree.append(row)
reduce(iadd, reversed(tree), self._index)
self._offset = size * 2 - 1
def __delitem__(self, index):
if isinstance(index, slice):
start, stop, step = index.indices(self._len)
if step == 1 and start < stop:
if start == 0 and stop == self._len:
return self._clear()
elif self._len <= 8 * (stop - start):
values = self._getitem(slice(None, start))
if stop < self._len:
values += self._getitem(slice(stop, None))
self._clear()
return self._update(values)
indices = range(start, stop, step)
# Delete items from greatest index to least so
# that the indices remain valid throughout iteration.
if step > 0:
indices = reversed(indices)
_pos, _delete = self._pos, self._delete
for index in indices:
pos, idx = _pos(index)
_delete(pos, idx)
else:
pos, idx = self._pos(index)
self._delete(pos, idx)
def __getitem__(self, index):
"""Lookup value at `index` in sorted list.
``sl.__getitem__(index)`` <==> ``sl[index]``
Supports slicing.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList('abcde')
>>> sl[1]
'b'
>>> sl[-1]
'e'
>>> sl[2:5]
['c', 'd', 'e']
:param index: integer or slice for indexing
:return: value or list of values
:raises IndexError: if index out of range
"""
_lists = self._lists
if isinstance(index, slice):
start, stop, step = index.indices(self._len)
if step == 1 and start < stop:
# Whole slice optimization: start to stop slices the whole
# sorted list.
if start == 0 and stop == self._len:
return reduce(iadd, self._lists, [])
start_pos, start_idx = self._pos(start)
start_list = _lists[start_pos]
stop_idx = start_idx + stop - start
# Small slice optimization: start index and stop index are
# within the start list.
if len(start_list) >= stop_idx:
return start_list[start_idx:stop_idx]
if stop == self._len:
stop_pos = len(_lists) - 1
stop_idx = len(_lists[stop_pos])
else:
stop_pos, stop_idx = self._pos(stop)
prefix = _lists[start_pos][start_idx:]
middle = _lists[(start_pos + 1):stop_pos]
result = reduce(iadd, middle, prefix)
result += _lists[stop_pos][:stop_idx]
return result
if step == -1 and start > stop:
result = self._getitem(slice(stop + 1, start + 1))
result.reverse()
return result
# Return a list because a negative step could
# reverse the order of the items and this could
# be the desired behavior.
indices = range(start, stop, step)
return list(self._getitem(index) for index in indices)
else:
if self._len:
if index == 0:
return _lists[0][0]
elif index == -1:
return _lists[-1][-1]
else:
raise IndexError('list index out of range')
if 0 <= index < len(_lists[0]):
return _lists[0][index]
len_last = len(_lists[-1])
if -len_last < index < 0:
return _lists[-1][len_last + index]
pos, idx = self._pos(index)
return _lists[pos][idx]
_getitem = __getitem__
def __setitem__(self, index, value):
"""Raise not-implemented error.
``sl.__setitem__(index, value)`` <==> ``sl[index] = value``
:raises NotImplementedError: use ``del sl[index]`` and
``sl.add(value)`` instead
"""
message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
raise NotImplementedError(message)
def __iter__(self):
"""Return an iterator over the sorted list.
``sl.__iter__()`` <==> ``iter(sl)``
Iterating the sorted list while adding or deleting values may raise a
:exc:`RuntimeError` or fail to iterate over all values.
"""
return chain.from_iterable(self._lists)
def __reversed__(self):
"""Return a reverse iterator over the sorted list.
``sl.__reversed__()`` <==> ``reversed(sl)``
Iterating the sorted list while adding or deleting values may raise a
:exc:`RuntimeError` or fail to iterate over all values.
"""
return chain.from_iterable(map(reversed, reversed(self._lists)))
def reverse(self):
"""Raise not-implemented error.
Sorted list maintains values in ascending sort order. Values may not be
reversed in-place.
Use ``reversed(sl)`` for an iterator over values in descending sort
order.
Implemented to override `MutableSequence.reverse` which provides an
erroneous default implementation.
:raises NotImplementedError: use ``reversed(sl)`` instead
"""
raise NotImplementedError('use ``reversed(sl)`` instead')
def islice(self, start=None, stop=None, reverse=False):
"""Return an iterator that slices sorted list from `start` to `stop`.
The `start` and `stop` index are treated inclusive and exclusive,
respectively.
Both `start` and `stop` default to `None` which is automatically
inclusive of the beginning and end of the sorted list.
When `reverse` is `True` the values are yielded from the iterator in
reverse order; `reverse` defaults to `False`.
>>> sl = SortedList('abcdefghij')
>>> it = sl.islice(2, 6)
>>> list(it)
['c', 'd', 'e', 'f']
:param int start: start index (inclusive)
:param int stop: stop index (exclusive)
:param bool reverse: yield values in reverse order
:return: iterator
"""
_len = self._len
if not _len:
return iter(())
start, stop, _ = slice(start, stop).indices(self._len)
if start >= stop:
return iter(())
_pos = self._pos
min_pos, min_idx = _pos(start)
if stop == _len:
max_pos = len(self._lists) - 1
max_idx = len(self._lists[-1])
else:
max_pos, max_idx = _pos(stop)
return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
"""Return an iterator that slices sorted list using two index pairs.
The index pairs are (min_pos, min_idx) and (max_pos, max_idx), the
first inclusive and the latter exclusive. See `_pos` for details on how
an index is converted to an index pair.
When `reverse` is `True`, values are yielded from the iterator in
reverse order.
"""
_lists = self._lists
if min_pos > max_pos:
return iter(())
if min_pos == max_pos:
if reverse:
indices = reversed(range(min_idx, max_idx))
return map(_lists[min_pos].__getitem__, indices)
indices = range(min_idx, max_idx)
return map(_lists[min_pos].__getitem__, indices)
next_pos = min_pos + 1
if next_pos == max_pos:
if reverse:
min_indices = range(min_idx, len(_lists[min_pos]))
max_indices = range(max_idx)
return chain(
map(_lists[max_pos].__getitem__, reversed(max_indices)),
map(_lists[min_pos].__getitem__, reversed(min_indices)),
)
min_indices = range(min_idx, len(_lists[min_pos]))
max_indices = range(max_idx)
return chain(
map(_lists[min_pos].__getitem__, min_indices),
map(_lists[max_pos].__getitem__, max_indices),
)
if reverse:
min_indices = range(min_idx, len(_lists[min_pos]))
sublist_indices = range(next_pos, max_pos)
sublists = map(_lists.__getitem__, reversed(sublist_indices))
max_indices = range(max_idx)
return chain(
map(_lists[max_pos].__getitem__, reversed(max_indices)),
chain.from_iterable(map(reversed, sublists)),
map(_lists[min_pos].__getitem__, reversed(min_indices)),
)
min_indices = range(min_idx, len(_lists[min_pos]))
sublist_indices = range(next_pos, max_pos)
sublists = map(_lists.__getitem__, sublist_indices)
max_indices = range(max_idx)
return chain(
map(_lists[min_pos].__getitem__, min_indices),
chain.from_iterable(sublists),
map(_lists[max_pos].__getitem__, max_indices),
)
def irange(self, minimum=None, maximum=None, inclusive=(True, True),
reverse=False):
"""Create an iterator of values between `minimum` and `maximum`.
Both `minimum` and `maximum` default to `None` which is automatically
inclusive of the beginning and end of the sorted list.
The argument `inclusive` is a pair of booleans that indicates whether
the minimum and maximum ought to be included in the range,
respectively. The default is ``(True, True)`` such that the range is
inclusive of both minimum and maximum.
When `reverse` is `True` the values are yielded from the iterator in
reverse order; `reverse` defaults to `False`.
>>> sl = SortedList('abcdefghij')
>>> it = sl.irange('c', 'f')
>>> list(it)
['c', 'd', 'e', 'f']
:param minimum: minimum value to start iterating
:param maximum: maximum value to stop iterating
:param inclusive: pair of booleans
:param bool reverse: yield values in reverse order
:return: iterator
"""
_maxes = self._maxes
if not _maxes:
return iter(())
_lists = self._lists
# Calculate the minimum (pos, idx) pair. By default this location
# will be inclusive in our calculation.
if minimum is None:
min_pos = 0
min_idx = 0
else:
if inclusive[0]:
min_pos = bisect_left(_maxes, minimum)
if min_pos == len(_maxes):
return iter(())
min_idx = bisect_left(_lists[min_pos], minimum)
else:
min_pos = bisect_right(_maxes, minimum)
if min_pos == len(_maxes):
return iter(())
min_idx = bisect_right(_lists[min_pos], minimum)
# Calculate the maximum (pos, idx) pair. By default this location
# will be exclusive in our calculation.
if maximum is None:
max_pos = len(_maxes) - 1
max_idx = len(_lists[max_pos])
else:
if inclusive[1]:
max_pos = bisect_right(_maxes, maximum)
if max_pos == len(_maxes):
max_pos -= 1
max_idx = len(_lists[max_pos])
else:
max_idx = bisect_right(_lists[max_pos], maximum)
else:
max_pos = bisect_left(_maxes, maximum)
if max_pos == len(_maxes):
max_pos -= 1
max_idx = len(_lists[max_pos])
else:
max_idx = bisect_left(_lists[max_pos], maximum)
return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
def __len__(self):
"""Return the size of the sorted list.
``sl.__len__()`` <==> ``len(sl)``
:return: size of sorted list
"""
return self._len
def bisect_left(self, value):
"""Return an index to insert `value` in the sorted list.
If the `value` is already present, the insertion point will be before
(to the left of) any existing values.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList([10, 11, 12, 13, 14])
>>> sl.bisect_left(12)
2
:param value: insertion index of value in sorted list
:return: index
"""
_maxes = self._maxes
if not _maxes:
return 0
pos = bisect_left(_maxes, value)
if pos == len(_maxes):
return self._len
idx = bisect_left(self._lists[pos], value)
return self._loc(pos, idx)
def bisect_right(self, value):
"""Return an index to insert `value` in the sorted list.
Similar to `bisect_left`, but if `value` is already present, the
insertion point will be after (to the right of) any existing values.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList([10, 11, 12, 13, 14])
>>> sl.bisect_right(12)
3
:param value: insertion index of value in sorted list
:return: index
"""
_maxes = self._maxes
if not _maxes:
return 0
pos = bisect_right(_maxes, value)
if pos == len(_maxes):
return self._len
idx = bisect_right(self._lists[pos], value)
return self._loc(pos, idx)
bisect = bisect_right
_bisect_right = bisect_right
def count(self, value):
"""Return number of occurrences of `value` in the sorted list.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
>>> sl.count(3)
3
:param value: value to count in sorted list
:return: count
"""
_maxes = self._maxes
if not _maxes:
return 0
pos_left = bisect_left(_maxes, value)
if pos_left == len(_maxes):
return 0
_lists = self._lists
idx_left = bisect_left(_lists[pos_left], value)
pos_right = bisect_right(_maxes, value)
if pos_right == len(_maxes):
return self._len - self._loc(pos_left, idx_left)
idx_right = bisect_right(_lists[pos_right], value)
if pos_left == pos_right:
return idx_right - idx_left
right = self._loc(pos_right, idx_right)
left = self._loc(pos_left, idx_left)
return right - left
def copy(self):
"""Return a shallow copy of the sorted list.
Runtime complexity: `O(n)`
:return: new sorted list
"""
return self.__class__(self)
__copy__ = copy
def append(self, value):
"""Raise not-implemented error.
Implemented to override `MutableSequence.append` which provides an
erroneous default implementation.
:raises NotImplementedError: use ``sl.add(value)`` instead
"""
raise NotImplementedError('use ``sl.add(value)`` instead')
def extend(self, values):
"""Raise not-implemented error.
Implemented to override `MutableSequence.extend` which provides an
erroneous default implementation.
:raises NotImplementedError: use ``sl.update(values)`` instead
"""
raise NotImplementedError('use ``sl.update(values)`` instead')
def insert(self, index, value):
"""Raise not-implemented error.
:raises NotImplementedError: use ``sl.add(value)`` instead
"""
raise NotImplementedError('use ``sl.add(value)`` instead')
def pop(self, index=-1):
"""Remove and return value at `index` in sorted list.
Raise :exc:`IndexError` if the sorted list is empty or index is out of
range.
Negative indices are supported.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList('abcde')
>>> sl.pop()
'e'
>>> sl.pop(2)
'c'
>>> sl
SortedList(['a', 'b', 'd'])
:param int index: index of value (default -1)
:return: value
:raises IndexError: if index is out of range
"""
if not self._len:
raise IndexError('pop index out of range')
_lists = self._lists
if index == 0:
val = _lists[0][0]
self._delete(0, 0)
return val
if index == -1:
pos = len(_lists) - 1
loc = len(_lists[pos]) - 1
val = _lists[pos][loc]
self._delete(pos, loc)
return val
if 0 <= index < len(_lists[0]):
val = _lists[0][index]
self._delete(0, index)
return val
len_last = len(_lists[-1])
if -len_last < index < 0:
pos = len(_lists) - 1
loc = len_last + index
val = _lists[pos][loc]
self._delete(pos, loc)
return val
pos, idx = self._pos(index)
val = _lists[pos][idx]
self._delete(pos, idx)
return val
def index(self, value, start=None, stop=None):
"""Return first index of value in sorted list.
Raise ValueError if `value` is not present.
Index must be between `start` and `stop` for the `value` to be
considered present. The default value, None, for `start` and `stop`
indicate the beginning and end of the sorted list.
Negative indices are supported.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList('abcde')
>>> sl.index('d')
3
>>> sl.index('z')
Traceback (most recent call last):
...
ValueError: 'z' is not in list
:param value: value in sorted list
:param int start: start index (default None, start of sorted list)
:param int stop: stop index (default None, end of sorted list)
:return: index of value
:raises ValueError: if value is not present
"""
_len = self._len
if not _len:
raise ValueError('{0!r} is not in list'.format(value))
if start is None:
start = 0
if start < 0:
start += _len
if start < 0:
start = 0
if stop is None:
stop = _len
if stop < 0:
stop += _len
if stop > _len:
stop = _len
if stop <= start:
raise ValueError('{0!r} is not in list'.format(value))
_maxes = self._maxes
pos_left = bisect_left(_maxes, value)
if pos_left == len(_maxes):
raise ValueError('{0!r} is not in list'.format(value))
_lists = self._lists
idx_left = bisect_left(_lists[pos_left], value)
if _lists[pos_left][idx_left] != value:
raise ValueError('{0!r} is not in list'.format(value))
stop -= 1
left = self._loc(pos_left, idx_left)
if start <= left:
if left <= stop:
return left
else:
right = self._bisect_right(value) - 1
if start <= right:
return start
raise ValueError('{0!r} is not in list'.format(value))
def __add__(self, other):
"""Return new sorted list containing all values in both sequences.
``sl.__add__(other)`` <==> ``sl + other``
Values in `other` do not need to be in sorted order.
Runtime complexity: `O(n*log(n))`
>>> sl1 = SortedList('bat')
>>> sl2 = SortedList('cat')
>>> sl1 + sl2
SortedList(['a', 'a', 'b', 'c', 't', 't'])
:param other: other iterable
:return: new sorted list
"""
values = reduce(iadd, self._lists, [])
values.extend(other)
return self.__class__(values)
__radd__ = __add__
def __iadd__(self, other):
"""Update sorted list with values from `other`.
``sl.__iadd__(other)`` <==> ``sl += other``
Values in `other` do not need to be in sorted order.
Runtime complexity: `O(k*log(n))` -- approximate.
>>> sl = SortedList('bat')
>>> sl += 'cat'
>>> sl
SortedList(['a', 'a', 'b', 'c', 't', 't'])
:param other: other iterable
:return: existing sorted list
"""
self._update(other)
return self
def __mul__(self, num):
"""Return new sorted list with `num` shallow copies of values.
``sl.__mul__(num)`` <==> ``sl * num``
Runtime complexity: `O(n*log(n))`
>>> sl = SortedList('abc')
>>> sl * 3
SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
:param int num: count of shallow copies
:return: new sorted list
"""
values = reduce(iadd, self._lists, []) * num
return self.__class__(values)
__rmul__ = __mul__
def __imul__(self, num):
"""Update the sorted list with `num` shallow copies of values.
``sl.__imul__(num)`` <==> ``sl *= num``
Runtime complexity: `O(n*log(n))`
>>> sl = SortedList('abc')
>>> sl *= 3
>>> sl
SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
:param int num: count of shallow copies
:return: existing sorted list
"""
values = reduce(iadd, self._lists, []) * num
self._clear()
self._update(values)
return self
def __make_cmp(seq_op, symbol, doc):
"Make comparator method."
def comparer(self, other):
"Compare method for sorted list and sequence."
if not isinstance(other, Sequence):
return NotImplemented
self_len = self._len
len_other = len(other)
if self_len != len_other:
if seq_op is eq:
return False
if seq_op is ne:
return True
for alpha, beta in zip(self, other):
if alpha != beta:
return seq_op(alpha, beta)
return seq_op(self_len, len_other)
seq_op_name = seq_op.__name__
comparer.__name__ = '__{0}__'.format(seq_op_name)
doc_str = """Return true if and only if sorted list is {0} `other`.
``sl.__{1}__(other)`` <==> ``sl {2} other``
Comparisons use lexicographical order as with sequences.
Runtime complexity: `O(n)`
:param other: `other` sequence
:return: true if sorted list is {0} `other`
"""
comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
return comparer
__eq__ = __make_cmp(eq, '==', 'equal to')
__ne__ = __make_cmp(ne, '!=', 'not equal to')
__lt__ = __make_cmp(lt, '<', 'less than')
__gt__ = __make_cmp(gt, '>', 'greater than')
__le__ = __make_cmp(le, '<=', 'less than or equal to')
__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
__make_cmp = staticmethod(__make_cmp)
def __reduce__(self):
values = reduce(iadd, self._lists, [])
return (type(self), (values,))
@recursive_repr()
def __repr__(self):
"""Return string representation of sorted list.
``sl.__repr__()`` <==> ``repr(sl)``
:return: string representation
"""
return '{0}({1!r})'.format(type(self).__name__, list(self))
def _check(self):
"""Check invariants of sorted list.
Runtime complexity: `O(n)`
"""
try:
assert self._load >= 4
assert len(self._maxes) == len(self._lists)
assert self._len == sum(len(sublist) for sublist in self._lists)
# Check all sublists are sorted.
for sublist in self._lists:
for pos in range(1, len(sublist)):
assert sublist[pos - 1] <= sublist[pos]
# Check beginning/end of sublists are sorted.
for pos in range(1, len(self._lists)):
assert self._lists[pos - 1][-1] <= self._lists[pos][0]
# Check _maxes index is the last value of each sublist.
for pos in range(len(self._maxes)):
assert self._maxes[pos] == self._lists[pos][-1]
# Check sublist lengths are less than double load-factor.
double = self._load << 1
assert all(len(sublist) <= double for sublist in self._lists)
# Check sublist lengths are greater than half load-factor for all
# but the last sublist.
half = self._load >> 1
for pos in range(0, len(self._lists) - 1):
assert len(self._lists[pos]) >= half
if self._index:
assert self._len == self._index[0]
assert len(self._index) == self._offset + len(self._lists)
# Check index leaf nodes equal length of sublists.
for pos in range(len(self._lists)):
leaf = self._index[self._offset + pos]
assert leaf == len(self._lists[pos])
# Check index branch nodes are the sum of their children.
for pos in range(self._offset):
child = (pos << 1) + 1
if child >= len(self._index):
assert self._index[pos] == 0
elif child + 1 == len(self._index):
assert self._index[pos] == self._index[child]
else:
child_sum = self._index[child] + self._index[child + 1]
assert child_sum == self._index[pos]
except:
traceback.print_exc(file=sys.stdout)
print('len', self._len)
print('load', self._load)
print('offset', self._offset)
print('len_index', len(self._index))
print('index', self._index)
print('len_maxes', len(self._maxes))
print('maxes', self._maxes)
print('len_lists', len(self._lists))
print('lists', self._lists)
raise
def identity(value):
"Identity function."
return value
class SortedKeyList(SortedList):
"""Sorted-key list is a subtype of sorted list.
The sorted-key list maintains values in comparison order based on the
result of a key function applied to every value.
All the same methods that are available in :class:`SortedList` are also
available in :class:`SortedKeyList`.
Additional methods provided:
* :attr:`SortedKeyList.key`
* :func:`SortedKeyList.bisect_key_left`
* :func:`SortedKeyList.bisect_key_right`
* :func:`SortedKeyList.irange_key`
Some examples below use:
>>> from operator import neg
>>> neg
<built-in function neg>
>>> neg(1)
-1
"""
def __init__(self, iterable=None, key=identity):
"""Initialize sorted-key list instance.
Optional `iterable` argument provides an initial iterable of values to
initialize the sorted-key list.
Optional `key` argument defines a callable that, like the `key`
argument to Python's `sorted` function, extracts a comparison key from
each value. The default is the identity function.
Runtime complexity: `O(n*log(n))`
>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl
SortedKeyList([], key=<built-in function neg>)
>>> skl = SortedKeyList([3, 1, 2], key=neg)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
:param iterable: initial values (optional)
:param key: function used to extract comparison key (optional)
"""
self._key = key
self._len = 0
self._load = self.DEFAULT_LOAD_FACTOR
self._lists = []
self._keys = []
self._maxes = []
self._index = []
self._offset = 0
if iterable is not None:
self._update(iterable)
def __new__(cls, iterable=None, key=identity):
return object.__new__(cls)
@property
def key(self):
"Function used to extract comparison key from values."
return self._key
def clear(self):
"""Remove all values from sorted-key list.
Runtime complexity: `O(n)`
"""
self._len = 0
del self._lists[:]
del self._keys[:]
del self._maxes[:]
del self._index[:]
_clear = clear
def add(self, value):
"""Add `value` to sorted-key list.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl.add(3)
>>> skl.add(1)
>>> skl.add(2)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
:param value: value to add to sorted-key list
"""
_lists = self._lists
_keys = self._keys
_maxes = self._maxes
key = self._key(value)
if _maxes:
pos = bisect_right(_maxes, key)
if pos == len(_maxes):
pos -= 1
_lists[pos].append(value)
_keys[pos].append(key)
_maxes[pos] = key
else:
idx = bisect_right(_keys[pos], key)
_lists[pos].insert(idx, value)
_keys[pos].insert(idx, key)
self._expand(pos)
else:
_lists.append([value])
_keys.append([key])
_maxes.append(key)
self._len += 1
def _expand(self, pos):
"""Split sublists with length greater than double the load-factor.
Updates the index when the sublist length is less than double the load
level. This requires incrementing the nodes in a traversal from the
leaf node to the root. For an example traversal see
``SortedList._loc``.
"""
_lists = self._lists
_keys = self._keys
_index = self._index
if len(_keys[pos]) > (self._load << 1):
_maxes = self._maxes
_load = self._load
_lists_pos = _lists[pos]
_keys_pos = _keys[pos]
half = _lists_pos[_load:]
half_keys = _keys_pos[_load:]
del _lists_pos[_load:]
del _keys_pos[_load:]
_maxes[pos] = _keys_pos[-1]
_lists.insert(pos + 1, half)
_keys.insert(pos + 1, half_keys)
_maxes.insert(pos + 1, half_keys[-1])
del _index[:]
else:
if _index:
child = self._offset + pos
while child:
_index[child] += 1
child = (child - 1) >> 1
_index[0] += 1
def update(self, iterable):
"""Update sorted-key list by adding all values from `iterable`.
Runtime complexity: `O(k*log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl.update([3, 1, 2])
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
:param iterable: iterable of values to add
"""
_lists = self._lists
_keys = self._keys
_maxes = self._maxes
values = sorted(iterable, key=self._key)
if _maxes:
if len(values) * 4 >= self._len:
_lists.append(values)
values = reduce(iadd, _lists, [])
values.sort(key=self._key)
self._clear()
else:
_add = self.add
for val in values:
_add(val)
return
_load = self._load
_lists.extend(values[pos:(pos + _load)]
for pos in range(0, len(values), _load))
_keys.extend(list(map(self._key, _list)) for _list in _lists)
_maxes.extend(sublist[-1] for sublist in _keys)
self._len = len(values)
del self._index[:]
_update = update
def __contains__(self, value):
"""Return true if `value` is an element of the sorted-key list.
``skl.__contains__(value)`` <==> ``value in skl``
Runtime complexity: `O(log(n))`
>>> from operator import neg
>>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
>>> 3 in skl
True
:param value: search for value in sorted-key list
:return: true if `value` in sorted-key list
"""
_maxes = self._maxes
if not _maxes:
return False
key = self._key(value)
pos = bisect_left(_maxes, key)
if pos == len(_maxes):
return False
_lists = self._lists
_keys = self._keys
idx = bisect_left(_keys[pos], key)
len_keys = len(_keys)
len_sublist = len(_keys[pos])
while True:
if _keys[pos][idx] != key:
return False
if _lists[pos][idx] == value:
return True
idx += 1
if idx == len_sublist:
pos += 1
if pos == len_keys:
return False
len_sublist = len(_keys[pos])
idx = 0
def discard(self, value):
"""Remove `value` from sorted-key list if it is a member.
If `value` is not a member, do nothing.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.discard(1)
>>> skl.discard(0)
>>> skl == [5, 4, 3, 2]
True
:param value: `value` to discard from sorted-key list
"""
_maxes = self._maxes
if not _maxes:
return
key = self._key(value)
pos = bisect_left(_maxes, key)
if pos == len(_maxes):
return
_lists = self._lists
_keys = self._keys
idx = bisect_left(_keys[pos], key)
len_keys = len(_keys)
len_sublist = len(_keys[pos])
while True:
if _keys[pos][idx] != key:
return
if _lists[pos][idx] == value:
self._delete(pos, idx)
return
idx += 1
if idx == len_sublist:
pos += 1
if pos == len_keys:
return
len_sublist = len(_keys[pos])
idx = 0
def remove(self, value):
"""Remove `value` from sorted-key list; `value` must be a member.
If `value` is not a member, raise ValueError.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
>>> skl.remove(5)
>>> skl == [4, 3, 2, 1]
True
>>> skl.remove(0)
Traceback (most recent call last):
...
ValueError: 0 not in list
:param value: `value` to remove from sorted-key list
:raises ValueError: if `value` is not in sorted-key list
"""
_maxes = self._maxes
if not _maxes:
raise ValueError('{0!r} not in list'.format(value))
key = self._key(value)
pos = bisect_left(_maxes, key)
if pos == len(_maxes):
raise ValueError('{0!r} not in list'.format(value))
_lists = self._lists
_keys = self._keys
idx = bisect_left(_keys[pos], key)
len_keys = len(_keys)
len_sublist = len(_keys[pos])
while True:
if _keys[pos][idx] != key:
raise ValueError('{0!r} not in list'.format(value))
if _lists[pos][idx] == value:
self._delete(pos, idx)
return
idx += 1
if idx == len_sublist:
pos += 1
if pos == len_keys:
raise ValueError('{0!r} not in list'.format(value))
len_sublist = len(_keys[pos])
idx = 0
def _delete(self, pos, idx):
"""Delete value at the given `(pos, idx)`.
Combines lists that are less than half the load level.
Updates the index when the sublist length is more than half the load
level. This requires decrementing the nodes in a traversal from the
leaf node to the root. For an example traversal see
``SortedList._loc``.
:param int pos: lists index
:param int idx: sublist index
"""
_lists = self._lists
_keys = self._keys
_maxes = self._maxes
_index = self._index
keys_pos = _keys[pos]
lists_pos = _lists[pos]
del keys_pos[idx]
del lists_pos[idx]
self._len -= 1
len_keys_pos = len(keys_pos)
if len_keys_pos > (self._load >> 1):
_maxes[pos] = keys_pos[-1]
if _index:
child = self._offset + pos
while child > 0:
_index[child] -= 1
child = (child - 1) >> 1
_index[0] -= 1
elif len(_keys) > 1:
if not pos:
pos += 1
prev = pos - 1
_keys[prev].extend(_keys[pos])
_lists[prev].extend(_lists[pos])
_maxes[prev] = _keys[prev][-1]
del _lists[pos]
del _keys[pos]
del _maxes[pos]
del _index[:]
self._expand(prev)
elif len_keys_pos:
_maxes[pos] = keys_pos[-1]
else:
del _lists[pos]
del _keys[pos]
del _maxes[pos]
del _index[:]
def irange(self, minimum=None, maximum=None, inclusive=(True, True),
reverse=False):
"""Create an iterator of values between `minimum` and `maximum`.
Both `minimum` and `maximum` default to `None` which is automatically
inclusive of the beginning and end of the sorted-key list.
The argument `inclusive` is a pair of booleans that indicates whether
the minimum and maximum ought to be included in the range,
respectively. The default is ``(True, True)`` such that the range is
inclusive of both minimum and maximum.
When `reverse` is `True` the values are yielded from the iterator in
reverse order; `reverse` defaults to `False`.
>>> from operator import neg
>>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
>>> it = skl.irange(14.5, 11.5)
>>> list(it)
[14, 13, 12]
:param minimum: minimum value to start iterating
:param maximum: maximum value to stop iterating
:param inclusive: pair of booleans
:param bool reverse: yield values in reverse order
:return: iterator
"""
min_key = self._key(minimum) if minimum is not None else None
max_key = self._key(maximum) if maximum is not None else None
return self._irange_key(
min_key=min_key, max_key=max_key,
inclusive=inclusive, reverse=reverse,
)
def irange_key(self, min_key=None, max_key=None, inclusive=(True, True),
reverse=False):
"""Create an iterator of values between `min_key` and `max_key`.
Both `min_key` and `max_key` default to `None` which is automatically
inclusive of the beginning and end of the sorted-key list.
The argument `inclusive` is a pair of booleans that indicates whether
the minimum and maximum ought to be included in the range,
respectively. The default is ``(True, True)`` such that the range is
inclusive of both minimum and maximum.
When `reverse` is `True` the values are yielded from the iterator in
reverse order; `reverse` defaults to `False`.
>>> from operator import neg
>>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
>>> it = skl.irange_key(-14, -12)
>>> list(it)
[14, 13, 12]
:param min_key: minimum key to start iterating
:param max_key: maximum key to stop iterating
:param inclusive: pair of booleans
:param bool reverse: yield values in reverse order
:return: iterator
"""
_maxes = self._maxes
if not _maxes:
return iter(())
_keys = self._keys
# Calculate the minimum (pos, idx) pair. By default this location
# will be inclusive in our calculation.
if min_key is None:
min_pos = 0
min_idx = 0
else:
if inclusive[0]:
min_pos = bisect_left(_maxes, min_key)
if min_pos == len(_maxes):
return iter(())
min_idx = bisect_left(_keys[min_pos], min_key)
else:
min_pos = bisect_right(_maxes, min_key)
if min_pos == len(_maxes):
return iter(())
min_idx = bisect_right(_keys[min_pos], min_key)
# Calculate the maximum (pos, idx) pair. By default this location
# will be exclusive in our calculation.
if max_key is None:
max_pos = len(_maxes) - 1
max_idx = len(_keys[max_pos])
else:
if inclusive[1]:
max_pos = bisect_right(_maxes, max_key)
if max_pos == len(_maxes):
max_pos -= 1
max_idx = len(_keys[max_pos])
else:
max_idx = bisect_right(_keys[max_pos], max_key)
else:
max_pos = bisect_left(_maxes, max_key)
if max_pos == len(_maxes):
max_pos -= 1
max_idx = len(_keys[max_pos])
else:
max_idx = bisect_left(_keys[max_pos], max_key)
return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
_irange_key = irange_key
def bisect_left(self, value):
"""Return an index to insert `value` in the sorted-key list.
If the `value` is already present, the insertion point will be before
(to the left of) any existing values.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_left(1)
4
:param value: insertion index of value in sorted-key list
:return: index
"""
return self._bisect_key_left(self._key(value))
def bisect_right(self, value):
"""Return an index to insert `value` in the sorted-key list.
Similar to `bisect_left`, but if `value` is already present, the
insertion point will be after (to the right of) any existing values.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_right(1)
5
:param value: insertion index of value in sorted-key list
:return: index
"""
return self._bisect_key_right(self._key(value))
bisect = bisect_right
def bisect_key_left(self, key):
"""Return an index to insert `key` in the sorted-key list.
If the `key` is already present, the insertion point will be before (to
the left of) any existing keys.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_left(-1)
4
:param key: insertion index of key in sorted-key list
:return: index
"""
_maxes = self._maxes
if not _maxes:
return 0
pos = bisect_left(_maxes, key)
if pos == len(_maxes):
return self._len
idx = bisect_left(self._keys[pos], key)
return self._loc(pos, idx)
_bisect_key_left = bisect_key_left
def bisect_key_right(self, key):
"""Return an index to insert `key` in the sorted-key list.
Similar to `bisect_key_left`, but if `key` is already present, the
insertion point will be after (to the right of) any existing keys.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_right(-1)
5
:param key: insertion index of key in sorted-key list
:return: index
"""
_maxes = self._maxes
if not _maxes:
return 0
pos = bisect_right(_maxes, key)
if pos == len(_maxes):
return self._len
idx = bisect_right(self._keys[pos], key)
return self._loc(pos, idx)
bisect_key = bisect_key_right
_bisect_key_right = bisect_key_right
def count(self, value):
"""Return number of occurrences of `value` in the sorted-key list.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([4, 4, 4, 4, 3, 3, 3, 2, 2, 1], key=neg)
>>> skl.count(2)
2
:param value: value to count in sorted-key list
:return: count
"""
_maxes = self._maxes
if not _maxes:
return 0
key = self._key(value)
pos = bisect_left(_maxes, key)
if pos == len(_maxes):
return 0
_lists = self._lists
_keys = self._keys
idx = bisect_left(_keys[pos], key)
total = 0
len_keys = len(_keys)
len_sublist = len(_keys[pos])
while True:
if _keys[pos][idx] != key:
return total
if _lists[pos][idx] == value:
total += 1
idx += 1
if idx == len_sublist:
pos += 1
if pos == len_keys:
return total
len_sublist = len(_keys[pos])
idx = 0
def copy(self):
"""Return a shallow copy of the sorted-key list.
Runtime complexity: `O(n)`
:return: new sorted-key list
"""
return self.__class__(self, key=self._key)
__copy__ = copy
def index(self, value, start=None, stop=None):
"""Return first index of value in sorted-key list.
Raise ValueError if `value` is not present.
Index must be between `start` and `stop` for the `value` to be
considered present. The default value, None, for `start` and `stop`
indicate the beginning and end of the sorted-key list.
Negative indices are supported.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.index(2)
3
>>> skl.index(0)
Traceback (most recent call last):
...
ValueError: 0 is not in list
:param value: value in sorted-key list
:param int start: start index (default None, start of sorted-key list)
:param int stop: stop index (default None, end of sorted-key list)
:return: index of value
:raises ValueError: if value is not present
"""
_len = self._len
if not _len:
raise ValueError('{0!r} is not in list'.format(value))
if start is None:
start = 0
if start < 0:
start += _len
if start < 0:
start = 0
if stop is None:
stop = _len
if stop < 0:
stop += _len
if stop > _len:
stop = _len
if stop <= start:
raise ValueError('{0!r} is not in list'.format(value))
_maxes = self._maxes
key = self._key(value)
pos = bisect_left(_maxes, key)
if pos == len(_maxes):
raise ValueError('{0!r} is not in list'.format(value))
stop -= 1
_lists = self._lists
_keys = self._keys
idx = bisect_left(_keys[pos], key)
len_keys = len(_keys)
len_sublist = len(_keys[pos])
while True:
if _keys[pos][idx] != key:
raise ValueError('{0!r} is not in list'.format(value))
if _lists[pos][idx] == value:
loc = self._loc(pos, idx)
if start <= loc <= stop:
return loc
elif loc > stop:
break
idx += 1
if idx == len_sublist:
pos += 1
if pos == len_keys:
raise ValueError('{0!r} is not in list'.format(value))
len_sublist = len(_keys[pos])
idx = 0
raise ValueError('{0!r} is not in list'.format(value))
def __add__(self, other):
"""Return new sorted-key list containing all values in both sequences.
``skl.__add__(other)`` <==> ``skl + other``
Values in `other` do not need to be in sorted-key order.
Runtime complexity: `O(n*log(n))`
>>> from operator import neg
>>> skl1 = SortedKeyList([5, 4, 3], key=neg)
>>> skl2 = SortedKeyList([2, 1, 0], key=neg)
>>> skl1 + skl2
SortedKeyList([5, 4, 3, 2, 1, 0], key=<built-in function neg>)
:param other: other iterable
:return: new sorted-key list
"""
values = reduce(iadd, self._lists, [])
values.extend(other)
return self.__class__(values, key=self._key)
__radd__ = __add__
def __mul__(self, num):
"""Return new sorted-key list with `num` shallow copies of values.
``skl.__mul__(num)`` <==> ``skl * num``
Runtime complexity: `O(n*log(n))`
>>> from operator import neg
>>> skl = SortedKeyList([3, 2, 1], key=neg)
>>> skl * 2
SortedKeyList([3, 3, 2, 2, 1, 1], key=<built-in function neg>)
:param int num: count of shallow copies
:return: new sorted-key list
"""
values = reduce(iadd, self._lists, []) * num
return self.__class__(values, key=self._key)
def __reduce__(self):
values = reduce(iadd, self._lists, [])
return (type(self), (values, self.key))
@recursive_repr()
def __repr__(self):
"""Return string representation of sorted-key list.
``skl.__repr__()`` <==> ``repr(skl)``
:return: string representation
"""
type_name = type(self).__name__
return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)
def _check(self):
"""Check invariants of sorted-key list.
Runtime complexity: `O(n)`
"""
try:
assert self._load >= 4
assert len(self._maxes) == len(self._lists) == len(self._keys)
assert self._len == sum(len(sublist) for sublist in self._lists)
# Check all sublists are sorted.
for sublist in self._keys:
for pos in range(1, len(sublist)):
assert sublist[pos - 1] <= sublist[pos]
# Check beginning/end of sublists are sorted.
for pos in range(1, len(self._keys)):
assert self._keys[pos - 1][-1] <= self._keys[pos][0]
# Check _keys matches _key mapped to _lists.
for val_sublist, key_sublist in zip(self._lists, self._keys):
assert len(val_sublist) == len(key_sublist)
for val, key in zip(val_sublist, key_sublist):
assert self._key(val) == key
# Check _maxes index is the last value of each sublist.
for pos in range(len(self._maxes)):
assert self._maxes[pos] == self._keys[pos][-1]
# Check sublist lengths are less than double load-factor.
double = self._load << 1
assert all(len(sublist) <= double for sublist in self._lists)
# Check sublist lengths are greater than half load-factor for all
# but the last sublist.
half = self._load >> 1
for pos in range(0, len(self._lists) - 1):
assert len(self._lists[pos]) >= half
if self._index:
assert self._len == self._index[0]
assert len(self._index) == self._offset + len(self._lists)
# Check index leaf nodes equal length of sublists.
for pos in range(len(self._lists)):
leaf = self._index[self._offset + pos]
assert leaf == len(self._lists[pos])
# Check index branch nodes are the sum of their children.
for pos in range(self._offset):
child = (pos << 1) + 1
if child >= len(self._index):
assert self._index[pos] == 0
elif child + 1 == len(self._index):
assert self._index[pos] == self._index[child]
else:
child_sum = self._index[child] + self._index[child + 1]
assert child_sum == self._index[pos]
except:
traceback.print_exc(file=sys.stdout)
print('len', self._len)
print('load', self._load)
print('offset', self._offset)
print('len_index', len(self._index))
print('index', self._index)
print('len_maxes', len(self._maxes))
print('maxes', self._maxes)
print('len_keys', len(self._keys))
print('keys', self._keys)
print('len_lists', len(self._lists))
print('lists', self._lists)
raise
SortedListWithKey = SortedKeyList
N=int(input())
A=list(map(int,input().split()))
def solve(X):
S=SortedList(X)
MAXX=S[-1]
S.discard(MAXX)
while len(S)>1:
MIN=S[0]
MAX=S[-1]
S.discard(MIN)
S.discard(MAX)
S.add(MIN+MAX)
if S[0]<=0 and MAXX>=0:
return True
else:
return False
if solve(A) or solve(list(map(lambda x:-x,A))):
print("Yes")
else:
print("No")