このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。
問題
ポイント
実直に解くのならば、はじめに1000x1000のマス目を用意し、紙の情報が与えられる度に重なっている全てのマスを+1していけば良いですが、残念ながらそれだとTLEとなります。
そこで、紙の情報が与えられた時、4隅のマスだけ値を更新して、最後に累積和を取ることを考えたいと思います。と言っても分かりにくいと思うので、図で説明します。
まず、紙の情報が与えられた時、以下の様にマスの値を更新します。※青枠が紙
すると、紙が置かれたマス目だけ最終的に1が置かれた状態となります。
上記のやり方を利用して
①全部の紙の情報を取得、それぞれ4隅の値を更新
②1000x1000マスの左から順に累積和を取得
③1000x1000マスの上から順に累積和を取得
といったやり方で解いていきます。
上記を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
# 最初にマス目を用意
cnt = [[0] * 1001 for _ in range(1001)]
# 紙の情報が与えられる度4隅の情報を更新
N = int(input())
for _ in range(N):
lx, ly, rx, ry = map(int, input().split())
cnt[lx][ly] += 1
cnt[lx][ry] -= 1
cnt[rx][ry] += 1
cnt[rx][ly] -= 1
# 横方向に累積和を取る
for i in range(1001):
for j in range(1, 1001):
cnt[i][j] += cnt[i][j-1]
# 縦方向に累積和を取る
for i in range(1, 1001):
for j in range(1001):
cnt[i][j] += cnt[i-1][j]
# マスを全探索してk枚重なっているマス目の総面積を求める マスの面積は1なのでマスの数=マスの総面積
ans = [0] * (N+1)
for i in range(1001):
for j in range(1001):
ans[cnt[i][j]] += 1
print(*ans[1:], sep='\n')
if __name__ == '__main__':
main()
