ABC388 E — Simultaneous Kagamimochi

1# -*- coding: utf-8 -*-2 3import math4from bisect import bisect_left, bisect_right, insort5from typing import Generic, Iterable, Iterator, List, TypeVar, Union6 7T = TypeVar("T")8 9 10class SortedMultiset(Generic[T]):11    """Sorted multi set (set) in C++.12 13    See:14    https://qiita.com/tatyam/items/492c70ac4c955c05560215    https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py16    """17 18    BUCKET_RATIO = 5019    REBUILD_RATIO = 17020 21    def _build(self, a=None) -> None:22        "Evenly divide `a` into buckets."23        if a is None:24            a = list(self)25 26        size = self.size = len(a)27        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))28        self.a = [29            a[size * i // bucket_size : size * (i + 1) // bucket_size]30            for i in range(bucket_size)31        ]32 33    def __init__(self, a: Iterable[T] = []) -> None:34        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"35        a = list(a)36 37        if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):  # type: ignore38            a = sorted(a)  # type: ignore39 40        self._build(a)41 42    def __iter__(self) -> Iterator[T]:43        for i in self.a:44            for j in i:45                yield j  # type: ignore46 47    def __reversed__(self) -> Iterator[T]:48        for i in reversed(self.a):49            for j in reversed(i):50                yield j51 52    def __len__(self) -> int:53        return self.size54 55    def __repr__(self) -> str:56        return "SortedMultiset" + str(self.a)57 58    def __str__(self) -> str:59        s = str(list(self))60        return "{" + s[1 : len(s) - 1] + "}"61 62    def _find_bucket(self, x: T) -> List[T]:63        "Find the bucket which should contain x. self must not be empty."64        for a in self.a:65            if x <= a[-1]:  # type: ignore66                return a67        return a  # type: ignore68 69    def __contains__(self, x: T) -> bool:70        if self.size == 0:71            return False72 73        a = self._find_bucket(x)74        i = bisect_left(a, x)  # type: ignore75        return i != len(a) and a[i] == x76 77    def count(self, x: T) -> int:78        "Count the number of x."79        return self.index_right(x) - self.index(x)80 81    def add(self, x: T) -> None:82        "Add an element. / O(√N)"83        if self.size == 0:84            self.a = [[x]]85            self.size = 186            return87 88        a = self._find_bucket(x)89        insort(a, x)  # type: ignore90        self.size += 191 92        if len(a) > len(self.a) * self.REBUILD_RATIO:93            self._build()94 95    def discard(self, x: T) -> bool:96        "Remove an element and return True if removed. / O(√N)"97        if self.size == 0:98            return False99 100        a = self._find_bucket(x)101        i = bisect_left(a, x)  # type: ignore102 103        if i == len(a) or a[i] != x:104            return False105 106        a.pop(i)107        self.size -= 1108 109        if len(a) == 0:110            self._build()111 112        return True113 114    def lt(self, x: T) -> Union[T, None]:115        "Find the largest element < x, or None if it doesn't exist."116        for a in reversed(self.a):117            if a[0] < x:  # type: ignore118                return a[bisect_left(a, x) - 1]  # type: ignore119        return None120 121    def le(self, x: T) -> Union[T, None]:122        "Find the largest element <= x, or None if it doesn't exist."123        for a in reversed(self.a):124            if a[0] <= x:  # type: ignore125                return a[bisect_right(a, x) - 1]  # type: ignore126        return None127 128    def gt(self, x: T) -> Union[T, None]:129        "Find the smallest element > x, or None if it doesn't exist."130        for a in self.a:131            if a[-1] > x:  # type: ignore132                return a[bisect_right(a, x)]  # type: ignore133        return None134 135    def ge(self, x: T) -> Union[T, None]:136        "Find the smallest element >= x, or None if it doesn't exist."137        for a in self.a:138            if a[-1] >= x:  # type: ignore139                return a[bisect_left(a, x)]  # type: ignore140        return None141 142    def __getitem__(self, x: int) -> T:143        "Return the x-th element, or IndexError if it doesn't exist."144        if x < 0:145            x += self.size146        if x < 0:147            raise IndexError148 149        for a in self.a:150            if x < len(a):151                return a[x]  # type: ignore152 153            x -= len(a)154        raise IndexError155 156    def index(self, x: T) -> int:157        "Count the number of elements < x."158        ans = 0159 160        for a in self.a:161            if a[-1] >= x:  # type: ignore162                return ans + bisect_left(a, x)  # type: ignore163            ans += len(a)164        return ans165 166    def index_right(self, x: T) -> int:167        "Count the number of elements <= x."168        ans = 0169 170        for a in self.a:171            if a[-1] > x:  # type: ignore172                return ans + bisect_right(a, x)  # type: ignore173            ans += len(a)174        return ans175 176 177def main():178    import sys179 180    input = sys.stdin.readline181 182    n = int(input())183    a = list(map(int, input().split()))184    mid = n // 2185    left, right = a[:mid], a[mid:]186    s = SortedMultiset(right)187    ans = 0188 189    for li in left:190        value = s.ge(li * 2)191 192        if value is None:193            break194 195        s.discard(value)196        ans += 1197 198    print(ans)199 200if __name__ == "__main__":201    main()202