筆者はレート800前後の茶～緑コーダ
ABC434のD問題を解いていく
実装コード
雲の領域を塗りつぶすために、2 次元 imos 法を用いる。
いくつの領域が重なっているかを数える cc と、
重なっている領域の番号の総和を管理する ck を用いる。
-
cc[i][j]が 0 のときは、どの雲にも覆われていないマス -
cc[i][j]が 1 のときは、ちょうど 1 つの雲だけが覆っているマスで、その雲の番号がck[i][j]になっている
と判断できるので、これらの値を数えて回答すればOK
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
M = 2000
K = M+10
def main():
N = rI()
cc=[[0]*K for _ in range(K)]
ck=[[0]*K for _ in range(K)]
for i in range(1,N+1):
u, d, l, r = rLI()
d+=1
r+=1
cc[u][l] += 1
cc[u][r] -= 1
cc[d][l] -= 1
cc[d][r] += 1
ck[u][l] += i
ck[u][r] -= i
ck[d][l] -= i
ck[d][r] += i
for i in range(K-1):
for j in range(K-1):
cc[i][j+1] += cc[i][j]
ck[i][j+1] += ck[i][j]
for i in range(K-1):
for j in range(K-1):
cc[i+1][j] += cc[i][j]
ck[i+1][j] += ck[i][j]
ans = [0] * -~N
for i in range(1,M+1):
for j in range(1,M+1):
if cc[i][j] == 0:
ans[0] += 1
if cc[i][j] == 1:
ans[ck[i][j]] += 1
for i in range(N):
print(ans[0]+ans[i+1])
if __name__ == '__main__':
main()
感想
cc,ckの 2 種類の imos 法を回す発想は思いつかなかった。
imos 法のデバッグに、思ったより時間を費やしてしまった。
1 次元 imos 法なら、累積和の派生系みたいな感覚で簡単なのに、2 次元に増えるだけで一気に複雑に感じる。