結果
| 問題 | No.2549 Paint Eggs |
| ユーザー |
 nakanoj
|
| 提出日時 | 2023-11-25 14:21:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,645 ms / 2,000 ms |
| コード長 | 44,080 bytes |
| コンパイル時間 | 416 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 176,604 KB |
| 最終ジャッジ日時 | 2024-09-26 10:42:30 |
| 合計ジャッジ時間 | 42,433 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 111 ms
78,080 KB |
| testcase_01 | AC | 135 ms
78,464 KB |
| testcase_02 | AC | 106 ms
77,776 KB |
| testcase_03 | AC | 116 ms
77,660 KB |
| testcase_04 | AC | 113 ms
78,080 KB |
| testcase_05 | AC | 121 ms
78,080 KB |
| testcase_06 | AC | 140 ms
78,336 KB |
| testcase_07 | AC | 122 ms
78,208 KB |
| testcase_08 | AC | 109 ms
77,840 KB |
| testcase_09 | AC | 134 ms
78,400 KB |
| testcase_10 | AC | 708 ms
148,372 KB |
| testcase_11 | AC | 947 ms
144,276 KB |
| testcase_12 | AC | 792 ms
121,396 KB |
| testcase_13 | AC | 809 ms
137,752 KB |
| testcase_14 | AC | 606 ms
113,912 KB |
| testcase_15 | AC | 348 ms
83,272 KB |
| testcase_16 | AC | 671 ms
132,464 KB |
| testcase_17 | AC | 708 ms
118,272 KB |
| testcase_18 | AC | 517 ms
117,392 KB |
| testcase_19 | AC | 717 ms
121,984 KB |
| testcase_20 | AC | 1,107 ms
166,492 KB |
| testcase_21 | AC | 1,147 ms
166,492 KB |
| testcase_22 | AC | 1,388 ms
160,488 KB |
| testcase_23 | AC | 1,397 ms
162,704 KB |
| testcase_24 | AC | 1,577 ms
154,212 KB |
| testcase_25 | AC | 816 ms
176,604 KB |
| testcase_26 | AC | 835 ms
176,324 KB |
| testcase_27 | AC | 989 ms
173,544 KB |
| testcase_28 | AC | 1,393 ms
159,684 KB |
| testcase_29 | AC | 1,030 ms
169,428 KB |
| testcase_30 | AC | 1,328 ms
159,204 KB |
| testcase_31 | AC | 1,074 ms
171,616 KB |
| testcase_32 | AC | 1,302 ms
166,272 KB |
| testcase_33 | AC | 1,129 ms
169,568 KB |
| testcase_34 | AC | 961 ms
173,780 KB |
| testcase_35 | AC | 1,593 ms
158,064 KB |
| testcase_36 | AC | 1,423 ms
162,724 KB |
| testcase_37 | AC | 1,257 ms
167,904 KB |
| testcase_38 | AC | 1,025 ms
171,376 KB |
| testcase_39 | AC | 1,162 ms
169,440 KB |
| testcase_40 | AC | 1,424 ms
154,332 KB |
| testcase_41 | AC | 1,645 ms
154,576 KB |
| testcase_42 | AC | 1,585 ms
154,772 KB |
| testcase_43 | AC | 1,599 ms
154,712 KB |
| testcase_44 | AC | 1,597 ms
154,180 KB |
ソースコード
# pylint: disable=too-many-lines
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
###############################################################################
# BEGIN Python 2/3 Shims
###############################################################################
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='...'):
"Decorator to make a repr function return fillvalue for a recursive call."
# pylint: disable=missing-docstring
# Copied from reprlib in Python 3
# https://hg.python.org/cpython/file/3.6/Lib/reprlib.py
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
###############################################################################
# END Python 2/3 Shims
###############################################################################
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):
# pylint: disable=unused-argument
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
# 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) >> 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):
_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):
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._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):
_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):
_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 self._len
def bisect_left(self, value):
_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):
_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):
_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 self.__class__(self)
__copy__ = copy
def 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._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):
_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):
values = reduce(iadd, self._lists, [])
values.extend(other)
return self.__class__(values)
__radd__ = __add__
def __iadd__(self, other):
self._update(other)
return self
def __mul__(self, num):
values = reduce(iadd, self._lists, []) * num
return self.__class__(values)
__rmul__ = __mul__
def __imul__(self, num):
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 '{0}({1!r})'.format(type(self).__name__, list(self))
def _check(self):
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):
def __init__(self, iterable=None, key=identity):
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):
self._len = 0
del self._lists[:]
del self._keys[:]
del self._maxes[:]
del self._index[:]
_clear = clear
def add(self, value):
_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):
_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):
_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):
_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):
_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):
_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):
_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):
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):
_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 self._bisect_key_left(self._key(value))
def bisect_right(self, value):
return self._bisect_key_right(self._key(value))
bisect = bisect_right
def bisect_key_left(self, key):
_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):
_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):
_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 self.__class__(self, key=self._key)
__copy__ = copy
def index(self, value, start=None, stop=None):
_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):
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, []) * 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):
type_name = type(self).__name__
return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)
def _check(self):
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
from collections import Counter
# from sortedcontainers import SortedList
def readints():
return list(map(int, input().split()))
def main():
N, M, K = readints()
C = [c - 1 for c in readints()]
A = readints()
count = Counter(C[:K])
costs = {}
for c, a in enumerate(A):
costs[c] = (K - count[c]) * a
win = SortedList(costs.values())
ans = win[0]
for i in range(K, N):
cin = C[i]
cout = C[i-K]
if cin == cout:
continue
win.remove(costs[cin])
win.remove(costs[cout])
costs[cout] += A[cout]
costs[cin] -= A[cin]
win.add(costs[cin])
win.add(costs[cout])
ans = min(ans, win[0])
print(ans)
if __name__ == '__main__':
# import sys
# sys.setrecursionlimit(550000)
# flush = lambda: sys.stdout.flush()
main()