ABC354 C — AtCoder Magics

1# -*- coding: utf-8 -*-2 3import math4from bisect import bisect_left, bisect_right5from typing import Generic, Iterable, Iterator, List, TypeVar, Union6 7T = TypeVar("T")8 9 10class SortedSet(Generic[T]):11    """Sorted set (set) in C++.12 13    See:14    https://qiita.com/tatyam/items/492c70ac4c955c05560215    https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.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 SortedSet from iterable.35        / O(N) if sorted and unique / O(N log N)36        """37        a = list(a)38 39        if not all(a[i] < a[i + 1] for i in range(len(a) - 1)):  # type: ignore40            a = sorted(set(a))  # type: ignore41 42        self._build(a)43 44    def __iter__(self) -> Iterator[T]:45        for i in self.a:46            for j in i:47                yield j  # type: ignore48 49    def __reversed__(self) -> Iterator[T]:50        for i in reversed(self.a):51            for j in reversed(i):52                yield j53 54    def __len__(self) -> int:55        return self.size56 57    def __repr__(self) -> str:58        return "SortedSet" + str(self.a)59 60    def __str__(self) -> str:61        s = str(list(self))62        return "{" + s[1 : len(s) - 1] + "}"63 64    def _find_bucket(self, x: T) -> List[T]:65        "Find the bucket which should contain x. self must not be empty."66        for a in self.a:67            if x <= a[-1]:  # type: ignore68                return a69        return a70 71    def __contains__(self, x: T) -> bool:72        if self.size == 0:73            return False74 75        a = self._find_bucket(x)76        i = bisect_left(a, x)  # type: ignore77 78        return i != len(a) and a[i] == x79 80    def add(self, x: T) -> bool:81        "Add an element and return True if added. / O(√N)"82        if self.size == 0:83            self.a = [[x]]84            self.size = 185            return True86 87        a = self._find_bucket(x)88        i = bisect_left(a, x)  # type: ignore89 90        if i != len(a) and a[i] == x:91            return False92 93        a.insert(i, x)94        self.size += 195 96        if len(a) > len(self.a) * self.REBUILD_RATIO:97            self._build()98 99        return True100 101    def discard(self, x: T) -> bool:102        "Remove an element and return True if removed. / O(√N)"103        if self.size == 0:104            return False105 106        a = self._find_bucket(x)107        i = bisect_left(a, x)  # type: ignore108 109        if i == len(a) or a[i] != x:110            return False111 112        a.pop(i)113        self.size -= 1114 115        if len(a) == 0:116            self._build()117        return True118 119    def lt(self, x: T) -> Union[T, None]:120        "Find the largest element < x, or None if it doesn't exist."121        for a in reversed(self.a):122            if a[0] < x:  # type: ignore123                return a[bisect_left(a, x) - 1]  # type: ignore124        return None125 126    def le(self, x: T) -> Union[T, None]:127        "Find the largest element <= x, or None if it doesn't exist."128        for a in reversed(self.a):129            if a[0] <= x:  # type: ignore130                return a[bisect_right(a, x) - 1]  # type: ignore131        return None132 133    def gt(self, x: T) -> Union[T, None]:134        "Find the smallest element > x, or None if it doesn't exist."135        for a in self.a:136            if a[-1] > x:  # type: ignore137                return a[bisect_right(a, x)]  # type: ignore138        return None139 140    def ge(self, x: T) -> Union[T, None]:141        "Find the smallest element >= x, or None if it doesn't exist."142        for a in self.a:143            if a[-1] >= x:  # type: ignore144                return a[bisect_left(a, x)]  # type: ignore145        return None146 147    def __getitem__(self, x: int) -> T:148        "Return the x-th element, or IndexError if it doesn't exist."149        if x < 0:150            x += self.size151        if x < 0:152            raise IndexError153 154        for a in self.a:155            if x < len(a):156                return a[x]  # type: ignore157 158            x -= len(a)159        raise IndexError160 161    def index(self, x: T) -> int:162        "Count the number of elements < x."163        ans = 0164 165        for a in self.a:166            if a[-1] >= x:  # type: ignore167                return ans + bisect_left(a, x)  # type: ignore168            ans += len(a)169        return ans170 171    def index_right(self, x: T) -> int:172        "Count the number of elements <= x."173        ans = 0174 175        for a in self.a:176            if a[-1] > x:  # type: ignore177                return ans + bisect_right(a, x)  # type: ignore178            ans += len(a)179        return ans180 181 182def main():183    import sys184 185    input = sys.stdin.readline186 187    n = int(input())188    ac = list()189    ans = set([i for i in range(1, n + 1)])190 191    for i in range(n):192        ai, ci = map(int, input().split())193        ac.append((ai, ci, i + 1))194 195    ac.sort(key=lambda x: -x[0])196    s = SortedSet([ac[0][1]])197 198    for i in range(1, n):199        _, ci, i = ac[i]200        result = s.lt(ci)201 202        if result is not None:203            ans.discard(i)204        else:205            s.add(ci)206 207    print(len(ans))208    print(*sorted(ans))209 210 211if __name__ == "__main__":212    main()213