競プロ典型90問：028 - Cluttered Paper（★4)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_ab

挑戦結果

• 挑戦日：2021/10/07
• 結果：解けた
• 時間：30分ぐらい

考えたこと

• いもす法というやつで解けるのでは？
• はっきりとおぼえていなかったけど、縦と横で累積和を取るはず

公式解説

• https://twitter.com/e869120/status/1388262816101007363

解説を読んだふりかえり

• やっぱりいもす法で良かった
• 実装で添字をミスっていて苦しんだけど、次回はスムーズにできるような気がする。

ソース

N = int(input())
# 紙を置く配列用のサイズ
M = 1000
# 2次元配列(いもす法)
A = [[0] * (M+2) for _ in range(M+2)]

# 下記のようにする。
# 左上:-1、右上:+1
# 左下:+1、右下:-1
for i in range(N):
    lx, ly, rx, ry = [int(x) for x in input().split()]
    A[lx][ly] += 1
    A[lx][ry] -= 1
    A[rx][ly] -= 1
    A[rx][ry] += 1

# 横向きに集計
for y in range(M+1):
    for x in range(M+1):
        A[x+1][y] += A[x][y]
# 縦向きに集計
for x in range(M+1):
    for y in range(M+1):
        A[x][y+1] += A[x][y]

# 各座標の枚数をカウントする
ans = [0] * (N+1)
for x in range(M+1):
    for y in range(M+1):
        ans[A[x][y]] += 1

# 結果の出力
for i in range(1, N+1):
    print(ans[i])