結果

問題 No.1074 増殖
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-10-14 13:11:01
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,300 bytes
コンパイル時間 322 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 69,376 KB
最終ジャッジ日時 2024-09-16 07:56:40
合計ジャッジ時間 2,337 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import List
from sortedcontainers import SortedList

INF = int(1e18)


class IncrementalRectangleUnionRange:
    __slots__ = ("_ur", "_ul", "_dr", "_dl")

    def __init__(self) -> None:
        self._ur = IncrementalRectangleUnion()
        self._ul = IncrementalRectangleUnion()
        self._dr = IncrementalRectangleUnion()
        self._dl = IncrementalRectangleUnion()

    def add(self, x1: int, x2: int, y1: int, y2: int) -> None:
        """Add [x1, x2] * [y1, y2].
        x1<=0<=x2.
        y1<=0<=y2.
        """
        assert x1 <= 0 <= x2, y1 <= 0 <= 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.sum


class IncrementalRectangleUnion:
    __slots__ = ("_sl", "sum")

    def __init__(self) -> None:
        self._sl = SortedList([(0, INF), (INF, 0)])
        self.sum = 0

    def 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:
            return
        nextY = item[1]
        pos -= 1
        pre = self._sl[pos]
        while pre[1] <= y:
            x1, y1 = pre
            del self._sl[pos]
            pos -= 1
            pre = self._sl[pos]
            self.sum -= (x1 - pre[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.sum


if __name__ == "__main__":
    # points = [(2, 2), (3, 4), (1, 7)]
    # ur = IncrementalRectangleUnionRange()
    # for x, y in points:
    #     ur.add(1, 3, 1, 3)
    #     print(ur.query())

    # https://yukicoder.me/problems/2577
    n = int(input())
    adds = [tuple(map(int, input().split())) for _ in range(n)]  # (x1,y1,x2,y2)
    UR = IncrementalRectangleUnionRange()
    pre = 0
    for x1, y1, x2, y2 in adds:
        UR.add(x1, x2, y1, y2)
        cur = UR.query()
        print(cur - pre)
        pre = cur
0