ABC170 E — Smart Infants

1# -*- coding: utf-8 -*-2 3 4from heapq import heapify, heappop, heappush5from typing import List, Optional6 7 8class DeletableHeapq:9    """Alternatives to ordered set (set) in C++.10 11    See:12    https://qiita.com/physharp/items/f9229ab879cac9a944d713    https://prd-xxx.hateblo.jp/entry/2019/06/24/23584414    """15 16    def __init__(self, descending_order=False) -> None:17        self.q: List[int] = []  # Body18        self.p: List[int] = []  # For deleting19        self.descending_order = descending_order20        self.sign = -1 if descending_order else 121 22    def build(self, a: List[int]) -> None:23        """Build a priority-queue q from an array."""24 25        if self.descending_order:26            a = [-ai for ai in a]27 28        self.q = a29        heapify(self.q)30 31    def push(self, number: int) -> None:32        """Add a number to the priority-queue."""33        heappush(self.q, number * self.sign)34 35    def erase(self, number: int) -> None:36        """Pseudo-erase a number to the priority-queue."""37        heappush(self.p, number * self.sign)38        self.clean()39 40    def clean(self) -> None:41        """Remove top elements from q, p."""42 43        while self.p and self.q[0] == self.p[0]:44            heappop(self.q)45            heappop(self.p)46 47    def pop(self, exc=None) -> Optional[int]:48        """Pop a top value from the priority-queue."""49        self.clean()50 51        if self.q:52            return heappop(self.q) * self.sign53        return exc54 55    def top(self, exc=None) -> Optional[int]:56        """Get a top value from the priority-queue.57 58        Note:59        descending_order=False: min value.60        descending_order=True : max value.61        """62        self.clean()63 64        if self.q:65            return self.q[0] * self.sign66        return exc67 68 69def main():70    import sys71 72    input = sys.stdin.readline73 74    n, q = map(int, input().split())75    g_count = 2 * 10 ** 576    groups = [DeletableHeapq(descending_order=True) for _ in range(g_count)]77    ab = list()78 79    for _ in range(n):80        ai, bi = map(int, input().split())81        bi -= 182        ab += [[ai, bi]]83 84        groups[bi].push(ai)85 86    equality = DeletableHeapq()87 88    # Get max value in each group.89    for group in groups:90        if group.q:91            equality.push(group.top())92 93    ans = list()94 95    for _ in range(q):96        ci, di = map(int, input().split())97        ci -= 198        di -= 199 100        rating, group_id = ab[ci]101 102        # Remove rating in group_id and max value in group_id of equality.103        equality.erase(groups[group_id].top())104        groups[group_id].erase(rating)105 106        # Get max value in group ci and add equality.107        if groups[group_id].q:108            equality.push(groups[group_id].top())109 110        # Update di from ci.111        ab[ci][1] = di112 113        # Remove max value in group_id of equality.114        if groups[di].q:115            equality.erase(groups[di].top())116 117        # Get max value in group di and add equality.118        groups[di].push(ab[ci][0])119        equality.push(groups[di].top())120 121        ans += [equality.top()]122 123    print(*ans, sep="\n")124 125 126if __name__ == "__main__":127    main()128