#920160 (Python3) No.1074 増殖

• 問題: No.1074 増殖
• ユーザー: 草苺奶昔
• 提出日時: 2023-10-14 13:10:46
• 言語: Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1)
• 結果: RE
• 実行時間: -
• コード長: 2,300 bytes
• コンパイル時間: 296 ms
• コンパイル使用メモリ: 12,800 KB
• 実行使用メモリ: 11,392 KB
• 最終ジャッジ日時: 2024-09-16 07:56:25
• 合計ジャッジ時間: 2,023 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	RE * 3
other	RE * 12

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX