結果

問題 No.3709 Unknown Treasure
コンテスト
ユーザー Rino-program
提出日時 2026-07-29 20:58:18
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 285 ms / 2,000 ms
+ 719µs
コード長 1,814 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 74 ms
コンパイル使用メモリ 81,152 KB
実行使用メモリ 146,816 KB
最終ジャッジ日時 2026-09-11 20:52:11
合計ジャッジ時間 7,326 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 2次元Imos法
# テンプレート(自作): https://github.com/Rino-program/atcoder/blob/main/contests/.template/template.py
class Imos2D:
    """概要:
        2次元いもす法（差分グリッド）を扱うクラス。

    メソッド:
        add(y1, x1, y2, x2, x): 矩形 [y1,y2)×[x1,x2) に x を加算予約する。
        build(): 全予約を反映した最終グリッドを返す。

    計算量:
        add は O(1)、build は O(HW)。

    補足:
        多数の矩形更新をまとめて処理したいときに有効。

    使用例:
        imos = Imos2D(H, W)
        imos.add(y1, x1, y2, x2, 1)  # [y1,y2) × [x1,x2) に +1
        result = imos.build()
    """
    def __init__(self, h: int, w: int):
        self.h = h
        self.w = w
        self.diff = [[0] * (w + 1) for _ in range(h + 1)]

    def add(self, y1: int, x1: int, y2: int, x2: int, x: int = 1) -> None:
        """[y1, y2) × [x1, x2) に x を加算（0-indexed）"""
        self.diff[y1][x1] += x
        self.diff[y1][x2] -= x
        self.diff[y2][x1] -= x
        self.diff[y2][x2] += x

    def build(self) -> list[list[int]]:
        """累積和を計算して結果を返す"""
        # 横方向
        for i in range(self.h):
            for j in range(self.w):
                self.diff[i][j + 1] += self.diff[i][j]
        # 縦方向
        for j in range(self.w):
            for i in range(self.h):
                self.diff[i + 1][j] += self.diff[i][j]
        return [row[:self.w] for row in self.diff[:self.h]]

H, W, N = map(int, input().split())
imos = Imos2D(H, W)
for _ in range(N):
    y1, x1, y2, x2 = map(int, input().split())
    imos.add(y1 - 1, x1 - 1, y2, x2)
result = imos.build()
ans = 0
for row in result:
    ans += sum(1 if x <= 0 else 0 for x in row)
print(ans)
0