結果
問題 | No.1736 Princess vs. Dragoness |
ユーザー |
![]() |
提出日時 | 2025-01-14 21:08:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 132 ms / 2,000 ms |
コード長 | 41,290 bytes |
コンパイル時間 | 363 ms |
コンパイル使用メモリ | 82,952 KB |
実行使用メモリ | 80,156 KB |
最終ジャッジ日時 | 2025-01-14 21:08:09 |
合計ジャッジ時間 | 5,047 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import sysimport tracebackfrom bisect import bisect_left, bisect_right, insortfrom collections.abc import MutableSequence, Sequencefrom functools import reducefrom itertools import chain, repeat, starmapfrom math import logfrom operator import add, eq, ge, gt, iadd, le, lt, nefrom reprlib import recursive_reprfrom textwrap import dedentclass SortedList(MutableSequence):DEFAULT_LOAD_FACTOR = 1000def __init__(self, iterable=None, key=None):assert key is Noneself._len = 0self._load = self.DEFAULT_LOAD_FACTORself._lists = []self._maxes = []self._index = []self._offset = 0if iterable is not None:self._update(iterable)def __new__(cls, iterable=None, key=None):# pylint: disable=unused-argumentif key is None:return object.__new__(cls)else:if cls is SortedList:return object.__new__(SortedKeyList)else:raise TypeError('inherit SortedKeyList for key argument')@propertydef key(self): # pylint: disable=useless-returnreturn Nonedef _reset(self, load):values = reduce(iadd, self._lists, [])self._clear()self._load = loadself._update(values)def clear(self):self._len = 0del self._lists[:]del self._maxes[:]del self._index[:]self._offset = 0_clear = cleardef add(self, value):_lists = self._lists_maxes = self._maxesif _maxes:pos = bisect_right(_maxes, value)if pos == len(_maxes):pos -= 1_lists[pos].append(value)_maxes[pos] = valueelse:insort(_lists[pos], value)self._expand(pos)else:_lists.append([value])_maxes.append(value)self._len += 1def _expand(self, pos):_load = self._load_lists = self._lists_index = self._indexif 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 + poswhile child:_index[child] += 1child = (child - 1) >> 1_index[0] += 1def update(self, iterable):_lists = self._lists_maxes = self._maxesvalues = sorted(iterable)if _maxes:if len(values) * 4 >= self._len:_lists.append(values)values = reduce(iadd, _lists, [])values.sort()self._clear()else:_add = self.addfor 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 = updatedef __contains__(self, value):_maxes = self._maxesif not _maxes:return Falsepos = bisect_left(_maxes, value)if pos == len(_maxes):return False_lists = self._listsidx = bisect_left(_lists[pos], value)return _lists[pos][idx] == valuedef discard(self, value):_maxes = self._maxesif not _maxes:returnpos = bisect_left(_maxes, value)if pos == len(_maxes):return_lists = self._listsidx = bisect_left(_lists[pos], value)if _lists[pos][idx] == value:self._delete(pos, idx)def remove(self, value):_maxes = self._maxesif not _maxes:raise ValueError(f'{value!r} not in list')pos = bisect_left(_maxes, value)if pos == len(_maxes):raise ValueError(f'{value!r} not in list')_lists = self._listsidx = bisect_left(_lists[pos], value)if _lists[pos][idx] == value:self._delete(pos, idx)else:raise ValueError(f'{value!r} not in list')def _delete(self, pos, idx):_lists = self._lists_maxes = self._maxes_index = self._index_lists_pos = _lists[pos]del _lists_pos[idx]self._len -= 1len_lists_pos = len(_lists_pos)if len_lists_pos > (self._load >> 1):_maxes[pos] = _lists_pos[-1]if _index:child = self._offset + poswhile child > 0:_index[child] -= 1child = (child - 1) >> 1_index[0] -= 1elif len(_lists) > 1:if not pos:pos += 1prev = 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._indexif not _index:self._build_index()total = 0# Increment pos to point in the index to len(self._lists[pos]).pos += self._offset# Iterate until reaching the root of the index tree at pos = 0.while pos:# Right-child nodes are at odd indices. At such indices# account the total below the left child node.if not pos & 1:total += _index[pos - 1]# Advance pos to the parent node.pos = (pos - 1) >> 1return total + idxdef _pos(self, idx):if idx < 0:last_len = len(self._lists[-1])if (-idx) <= last_len:return len(self._lists) - 1, last_len + idxidx += self._lenif 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._indexif not _index:self._build_index()pos = 0child = 1len_index = len(_index)while child < len_index:index_child = _index[child]if idx < index_child:pos = childelse:idx -= index_childpos = child + 1child = (pos << 1) + 1return (pos - self._offset, idx)def _build_index(self):row0 = list(map(len, self._lists))if len(row0) == 1:self._index[:] = row0self._offset = 0returnhead = 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 + row0self._offset = 1returnsize = 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 - 1def __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._deletefor index in indices:pos, idx = _pos(index)_delete(pos, idx)else:pos, idx = self._pos(index)self._delete(pos, idx)def __getitem__(self, index):_lists = self._listsif 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) - 1stop_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 resultif 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):message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'raise NotImplementedError(message)def __iter__(self):return chain.from_iterable(self._lists)def __reversed__(self):return chain.from_iterable(map(reversed, reversed(self._lists)))def reverse(self):raise NotImplementedError('use ``reversed(sl)`` instead')def islice(self, start=None, stop=None, reverse=False):_len = self._lenif not _len:return iter(())start, stop, _ = slice(start, stop).indices(self._len)if start >= stop:return iter(())_pos = self._posmin_pos, min_idx = _pos(start)if stop == _len:max_pos = len(self._lists) - 1max_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):_lists = self._listsif 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 + 1if 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):_maxes = self._maxesif 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 = 0min_idx = 0else: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) - 1max_idx = len(_lists[max_pos])else:if inclusive[1]:max_pos = bisect_right(_maxes, maximum)if max_pos == len(_maxes):max_pos -= 1max_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 -= 1max_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 self._lendef bisect_left(self, value):_maxes = self._maxesif not _maxes:return 0pos = bisect_left(_maxes, value)if pos == len(_maxes):return self._lenidx = bisect_left(self._lists[pos], value)return self._loc(pos, idx)def bisect_right(self, value):_maxes = self._maxesif not _maxes:return 0pos = bisect_right(_maxes, value)if pos == len(_maxes):return self._lenidx = bisect_right(self._lists[pos], value)return self._loc(pos, idx)bisect = bisect_right_bisect_right = bisect_rightdef count(self, value):_maxes = self._maxesif not _maxes:return 0pos_left = bisect_left(_maxes, value)if pos_left == len(_maxes):return 0_lists = self._listsidx_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_leftright = self._loc(pos_right, idx_right)left = self._loc(pos_left, idx_left)return right - leftdef copy(self):return self.__class__(self)__copy__ = copydef append(self, value):raise NotImplementedError('use ``sl.add(value)`` instead')def extend(self, values):raise NotImplementedError('use ``sl.update(values)`` instead')def insert(self, index, value):raise NotImplementedError('use ``sl.add(value)`` instead')def pop(self, index=-1):if not self._len:raise IndexError('pop index out of range')_lists = self._listsif index == 0:val = _lists[0][0]self._delete(0, 0)return valif index == -1:pos = len(_lists) - 1loc = len(_lists[pos]) - 1val = _lists[pos][loc]self._delete(pos, loc)return valif 0 <= index < len(_lists[0]):val = _lists[0][index]self._delete(0, index)return vallen_last = len(_lists[-1])if -len_last < index < 0:pos = len(_lists) - 1loc = len_last + indexval = _lists[pos][loc]self._delete(pos, loc)return valpos, idx = self._pos(index)val = _lists[pos][idx]self._delete(pos, idx)return valdef index(self, value, start=None, stop=None):_len = self._lenif not _len:raise ValueError(f'{value!r} is not in list')if start is None:start = 0if start < 0:start += _lenif start < 0:start = 0if stop is None:stop = _lenif stop < 0:stop += _lenif stop > _len:stop = _lenif stop <= start:raise ValueError(f'{value!r} is not in list')_maxes = self._maxespos_left = bisect_left(_maxes, value)if pos_left == len(_maxes):raise ValueError(f'{value!r} is not in list')_lists = self._listsidx_left = bisect_left(_lists[pos_left], value)if _lists[pos_left][idx_left] != value:raise ValueError(f'{value!r} is not in list')stop -= 1left = self._loc(pos_left, idx_left)if start <= left:if left <= stop:return leftelse:right = self._bisect_right(value) - 1if start <= right:return startraise ValueError(f'{value!r} is not in list')def __add__(self, other):values = reduce(iadd, self._lists, [])values.extend(other)return self.__class__(values)__radd__ = __add__def __iadd__(self, other):self._update(other)return selfdef __mul__(self, num):values = reduce(iadd, self._lists, []) * numreturn self.__class__(values)__rmul__ = __mul__def __imul__(self, num):values = reduce(iadd, self._lists, []) * numself._clear()self._update(values)return selfdef __make_cmp(seq_op, symbol, doc):def comparer(self, other):if not isinstance(other, Sequence):return NotImplementedself_len = self._lenlen_other = len(other)if self_len != len_other:if seq_op is eq:return Falseif seq_op is ne:return Truefor 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__ = f'__{seq_op_name}__'doc_str = """Return true if and only 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 f'{type(self).__name__}({list(self)!r})'def _check(self):try:assert self._load >= 4assert 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 << 1assert 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 >> 1for pos in range(0, len(self._lists) - 1):assert len(self._lists[pos]) >= halfif 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) + 1if child >= len(self._index):assert self._index[pos] == 0elif 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)raisedef identity(value):return valueclass SortedKeyList(SortedList):def __init__(self, iterable=None, key=identity):self._key = keyself._len = 0self._load = self.DEFAULT_LOAD_FACTORself._lists = []self._keys = []self._maxes = []self._index = []self._offset = 0if iterable is not None:self._update(iterable)def __new__(cls, iterable=None, key=identity):return object.__new__(cls)@propertydef key(self):return self._keydef clear(self):self._len = 0del self._lists[:]del self._keys[:]del self._maxes[:]del self._index[:]_clear = cleardef add(self, value):_lists = self._lists_keys = self._keys_maxes = self._maxeskey = 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] = keyelse: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 += 1def _expand(self, pos):_lists = self._lists_keys = self._keys_index = self._indexif 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 + poswhile child:_index[child] += 1child = (child - 1) >> 1_index[0] += 1def update(self, iterable):_lists = self._lists_keys = self._keys_maxes = self._maxesvalues = 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.addfor 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 = updatedef __contains__(self, value):_maxes = self._maxesif not _maxes:return Falsekey = self._key(value)pos = bisect_left(_maxes, key)if pos == len(_maxes):return False_lists = self._lists_keys = self._keysidx = bisect_left(_keys[pos], key)len_keys = len(_keys)len_sublist = len(_keys[pos])while True:if _keys[pos][idx] != key:return Falseif _lists[pos][idx] == value:return Trueidx += 1if idx == len_sublist:pos += 1if pos == len_keys:return Falselen_sublist = len(_keys[pos])idx = 0def discard(self, value):_maxes = self._maxesif not _maxes:returnkey = self._key(value)pos = bisect_left(_maxes, key)if pos == len(_maxes):return_lists = self._lists_keys = self._keysidx = bisect_left(_keys[pos], key)len_keys = len(_keys)len_sublist = len(_keys[pos])while True:if _keys[pos][idx] != key:returnif _lists[pos][idx] == value:self._delete(pos, idx)returnidx += 1if idx == len_sublist:pos += 1if pos == len_keys:returnlen_sublist = len(_keys[pos])idx = 0def remove(self, value):_maxes = self._maxesif not _maxes:raise ValueError(f'{value!r} not in list')key = self._key(value)pos = bisect_left(_maxes, key)if pos == len(_maxes):raise ValueError(f'{value!r} not in list')_lists = self._lists_keys = self._keysidx = bisect_left(_keys[pos], key)len_keys = len(_keys)len_sublist = len(_keys[pos])while True:if _keys[pos][idx] != key:raise ValueError(f'{value!r} not in list')if _lists[pos][idx] == value:self._delete(pos, idx)returnidx += 1if idx == len_sublist:pos += 1if pos == len_keys:raise ValueError(f'{value!r} not in list')len_sublist = len(_keys[pos])idx = 0def _delete(self, pos, idx):_lists = self._lists_keys = self._keys_maxes = self._maxes_index = self._indexkeys_pos = _keys[pos]lists_pos = _lists[pos]del keys_pos[idx]del lists_pos[idx]self._len -= 1len_keys_pos = len(keys_pos)if len_keys_pos > (self._load >> 1):_maxes[pos] = keys_pos[-1]if _index:child = self._offset + poswhile child > 0:_index[child] -= 1child = (child - 1) >> 1_index[0] -= 1elif len(_keys) > 1:if not pos:pos += 1prev = 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):min_key = self._key(minimum) if minimum is not None else Nonemax_key = self._key(maximum) if maximum is not None else Nonereturn 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):_maxes = self._maxesif 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 = 0min_idx = 0else: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) - 1max_idx = len(_keys[max_pos])else:if inclusive[1]:max_pos = bisect_right(_maxes, max_key)if max_pos == len(_maxes):max_pos -= 1max_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 -= 1max_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_keydef bisect_left(self, value):return self._bisect_key_left(self._key(value))def bisect_right(self, value):return self._bisect_key_right(self._key(value))bisect = bisect_rightdef bisect_key_left(self, key):_maxes = self._maxesif not _maxes:return 0pos = bisect_left(_maxes, key)if pos == len(_maxes):return self._lenidx = bisect_left(self._keys[pos], key)return self._loc(pos, idx)_bisect_key_left = bisect_key_leftdef bisect_key_right(self, key):_maxes = self._maxesif not _maxes:return 0pos = bisect_right(_maxes, key)if pos == len(_maxes):return self._lenidx = bisect_right(self._keys[pos], key)return self._loc(pos, idx)bisect_key = bisect_key_right_bisect_key_right = bisect_key_rightdef count(self, value):_maxes = self._maxesif not _maxes:return 0key = self._key(value)pos = bisect_left(_maxes, key)if pos == len(_maxes):return 0_lists = self._lists_keys = self._keysidx = bisect_left(_keys[pos], key)total = 0len_keys = len(_keys)len_sublist = len(_keys[pos])while True:if _keys[pos][idx] != key:return totalif _lists[pos][idx] == value:total += 1idx += 1if idx == len_sublist:pos += 1if pos == len_keys:return totallen_sublist = len(_keys[pos])idx = 0def copy(self):return self.__class__(self, key=self._key)__copy__ = copydef index(self, value, start=None, stop=None):_len = self._lenif not _len:raise ValueError(f'{value!r} is not in list')if start is None:start = 0if start < 0:start += _lenif start < 0:start = 0if stop is None:stop = _lenif stop < 0:stop += _lenif stop > _len:stop = _lenif stop <= start:raise ValueError(f'{value!r} is not in list')_maxes = self._maxeskey = self._key(value)pos = bisect_left(_maxes, key)if pos == len(_maxes):raise ValueError(f'{value!r} is not in list')stop -= 1_lists = self._lists_keys = self._keysidx = bisect_left(_keys[pos], key)len_keys = len(_keys)len_sublist = len(_keys[pos])while True:if _keys[pos][idx] != key:raise ValueError(f'{value!r} is not in list')if _lists[pos][idx] == value:loc = self._loc(pos, idx)if start <= loc <= stop:return locelif loc > stop:breakidx += 1if idx == len_sublist:pos += 1if pos == len_keys:raise ValueError(f'{value!r} is not in list')len_sublist = len(_keys[pos])idx = 0raise ValueError(f'{value!r} is not in list')def __add__(self, other):values = reduce(iadd, self._lists, [])values.extend(other)return self.__class__(values, key=self._key)__radd__ = __add__def __mul__(self, num):values = reduce(iadd, self._lists, []) * numreturn 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):type_name = type(self).__name__return f'{type_name}({list(self)!r}, key={self._key!r})'def _check(self):try:assert self._load >= 4assert 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 << 1assert 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 >> 1for pos in range(0, len(self._lists) - 1):assert len(self._lists[pos]) >= halfif 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) + 1if child >= len(self._index):assert self._index[pos] == 0elif 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)raiseN,A,B,X,Y = map(int,input().split())H = list(map(int,input().split()))S = SortedList(H)while S and S[-1] >= X and A > 0:tmp = S[-1]S.pop(-1)if tmp > X:S.add(tmp - X)A -= 1while S and B > 0:y = YB -= 1while S and y >= S[0]:y -= S[0]S.pop(0)if S:tmp = S[0]S.pop(0)S.add(tmp - y)if len(S) <= A:print("Yes")else:print("No")