典型90 028 – Cluttered Paper（★4）

競プロの精進のために学びがあった問題についてまとめています。目標は AtCoder 水色！

今のレートは茶色です。

問題

典型90 028 – Cluttered Paper（★4）を解きました。

考察

平面を面積1のブロックで構成された2次配列ととらえて、重なった紙の枚数分そのブロックの値を加算すれば、最終的にk枚の紙が重なっている部分の面積を求めることができる。

しかし、この実装の場合、最悪計算量がO(N^2)となるため、実行時間に間に合わない。

ここで、座標圧縮の考え方を平面に応用することで、縦と横のそれぞれに座圧を行うことを考える。

その場合、計算量は1000^2となるため、実行時間内に計算することができる。

コード

import pprint
N = int(input())
M = [[0]*(1000+1) for i in range(1000+1)]

for i in range(N):
    lx, ly, rx, ry = map(int,input().split())
    for i in range(ly, ry):
        M[i][lx] += 1
        M[i][rx] -= 1

ans = [0 for i in range(N+1)]
for m in M:
    t = 0
    for i in m:
        t += i
        ans[t] += 1

for i in range(1, N+1):
    print(ans[i])