結果
問題 | No.1074 増殖 |
ユーザー |
|
提出日時 | 2023-04-08 13:52:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 423 ms / 2,000 ms |
コード長 | 23,093 bytes |
コンパイル時間 | 379 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 90,068 KB |
最終ジャッジ日時 | 2024-10-03 08:25:02 |
合計ジャッジ時間 | 4,455 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
from bisect import bisect_left, bisect_right, insortfrom collections.abc import Sequencefrom functools import reducefrom itertools import chain, repeat, starmapfrom math import logfrom operator import add, eq, ge, gt, iadd, le, lt, nefrom textwrap import dedentfrom typing import Generic, Iterable, Optional, Tuple, TypeVarT = TypeVar("T")class SortedList(Generic[T]):DEFAULT_LOAD_FACTOR = 1000def __init__(self, iterable: Optional[Iterable[T]] = None):self._len = 0self._load = self.DEFAULT_LOAD_FACTORself._lists = [] # 分块self._maxes = [] # 各个分块的最大值self._index = []self._offset = 0if iterable is not None:self._update(iterable)def clear(self) -> None:self._len = 0del self._lists[:]del self._maxes[:]del self._index[:]self._offset = 0_clear = cleardef add(self, value: T) -> None:_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: int) -> None:_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: Iterable[T]) -> None:_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: T) -> bool:_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 remove(self, value: T) -> None:_maxes = self._maxesif 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._listsidx = 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 discard(self, value: T) -> None:_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 _delete(self, pos: int, idx: int) -> None:_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: int, idx: int) -> int:if not pos:return idx_index = self._indexif not _index:self._build_index()total = 0pos += self._offsetwhile pos:if not pos & 1:total += _index[pos - 1]pos = (pos - 1) >> 1return total + idxdef _pos(self, idx: int) -> Tuple[int, int]: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) -> None: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: int) -> None: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)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: int):_lists = self._listsif isinstance(index, slice):start, stop, step = index.indices(self._len)if step == 1 and start < stop: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 - startif 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 resultindices = 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 islice(self, start: Optional[T] = None, stop: Optional[T] = 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: Optional[T] = None,maximum: Optional[T] = None,inclusive=(True, True),reverse=False,):"""Create an iterator of values between `minimum` and `maximum`.>>> sl = SortedList('abcdefghij')>>> it = sl.irange('c', 'f')>>> list(it)['c', 'd', 'e', 'f']"""_maxes = self._maxesif not _maxes:return iter(())_lists = self._listsif 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)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: T) -> int:_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: T) -> int:_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: T) -> int:_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 pop(self, index=-1) -> T: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: T, start: Optional[int] = None, stop: Optional[int] = None) -> int:_len = self._lenif not _len:raise ValueError("{0!r} is not in list".format(value))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("{0!r} is not in list".format(value))_maxes = self._maxespos_left = bisect_left(_maxes, value)if pos_left == len(_maxes):raise ValueError("{0!r} is not in list".format(value))_lists = self._listsidx_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 -= 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("{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 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):"Make comparator method."def comparer(self, other):"zip逐项比较大小,如果大小一样,再比较长度"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__ = "__{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,))def __repr__(self) -> str:"""一般不会嵌套使用,所以这里没有用 `recursive_repr`"""return "{0}({1!r})".format(self.__class__.__name__, list(self))INF = int(1e18)class UnionRectangle:__slots__ = ("_sl", "sum")def __init__(self) -> None:self._sl = SortedList([(0, INF), (INF, 0)])self.sum = 0def add(self, x: int, y: int) -> None:"""Add [0, x] * [0, y]."""pos = self._sl.bisect_left((x, -INF))item = self._sl[pos]if item[1] >= y:returnnextY = item[1]pos -= 1while True:item = self._sl[pos]if item[1] > y:breakx1, y1 = itemdel self._sl[pos]pos -= 1self.sum -= (x1 - self._sl[pos][0]) * (y1 - nextY)self.sum += (x - self._sl[pos][0]) * (y - nextY)pos = self._sl.bisect_left((x, -INF))if self._sl[pos][0] == x:self._sl.pop(pos)self._sl.add((x, y))def query(self) -> int:"""Return the sum of all rectangles."""return self.sumclass UnionRectangleRange:__slots__ = ("_ur", "_ul", "_dr", "_dl")def __init__(self) -> None:self._ur = UnionRectangle()self._ul = UnionRectangle()self._dr = UnionRectangle()self._dl = UnionRectangle()def add(self, x1: int, x2: int, y1: int, y2: int) -> None:"""Add [x1, x2] * [y1, y2]."""self._ur.add(x2, y2)self._ul.add(-x1, y2)self._dr.add(x2, -y1)self._dl.add(-x1, -y1)def query(self) -> int:"""Return the sum of all rectangles."""return self._ur.sum + self._ul.sum + self._dr.sum + self._dl.sumif __name__ == "__main__":# points = [(2, 2), (3, 4), (1, 7)]# ur = UnionRectangleRange()# for x, y in points:# ur.add(1, 3, 1, 3)# print(ur.query())# https://yukicoder.me/problems/2577n = int(input())adds = [tuple(map(int, input().split())) for _ in range(n)] # (x1,y1,x2,y2)UR = UnionRectangleRange()pre = 0for x1, y1, x2, y2 in adds:UR.add(x1, x2, y1, y2)cur = UR.query()print(cur - pre)pre = cur