ABC325 D — Printing Machine

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    Landau notation: O(log(n))12 13    See:14    https://qiita.com/physharp/items/f9229ab879cac9a944d715    https://prd-xxx.hateblo.jp/entry/2019/06/24/23584416    """17 18    def __init__(self, descending_order=False) -> None:19        self.q: List[int] = []  # Body20        self.p: List[int] = []  # For deleting21        self.descending_order = descending_order22        self.sign = -1 if descending_order else 123 24    def build(self, a: List[int]) -> None:25        """Build a priority-queue q from an array."""26 27        if self.descending_order:28            a = [-ai for ai in a]29 30        self.q = a31        heapify(self.q)32 33    def push(self, number: int) -> None:34        """Add a number to the priority-queue."""35        heappush(self.q, number * self.sign)36 37    def erase(self, number: int) -> None:38        """Pseudo-erase a number to the priority-queue."""39        heappush(self.p, number * self.sign)40        self.clean()41 42    def clean(self) -> None:43        """Remove top elements from q, p."""44 45        while self.p and self.q[0] == self.p[0]:46            heappop(self.q)47            heappop(self.p)48 49    def pop(self, exc=None) -> Optional[int]:50        """Pop a top value from the priority-queue."""51        self.clean()52 53        if self.q:54            return heappop(self.q) * self.sign55        return exc56 57    def top(self, exc=None) -> Optional[int]:58        """Get a top value from the priority-queue.59 60        Landau notation: O(1)61 62        Note:63        descending_order=False: min value.64        descending_order=True : max value.65        """66        self.clean()67 68        if self.q:69            return self.q[0] * self.sign70        return exc71 72 73def main():74    import sys75 76    input = sys.stdin.readline77 78    n = int(input())79    lr = []80 81    for _ in range(n):82        ti, di = map(int, input().split())83        lr.append((ti, ti + di))84 85    # Greedy86    lr.sort()87 88    hq = DeletableHeapq()89    i, t = 0, 090    ans = 091 92    while i < n or hq.q:93        # li <= tである限り、キューにriを追加94        while i < n:95            li, ri = lr[i]96 97            if li > t:98                break99 100            hq.push(ri)101            i += 1102 103        # hq.top < tである限り、キューから削除104        while hq.q and hq.top() < t:105            hq.pop()106 107        # キューに要素が残っているなら答えに+1、要素を削除108        if hq.q:109            ans += 1110            hq.pop()111 112        # キューが空なら、tを進める113        if i < n and not hq.q:114            lj, _ = lr[i]115            t = lj116        else:117            t += 1118 119    print(ans)120 121 122if __name__ == "__main__":123    main()124