028 - Cluttered Paper(★4)

# いもす法

キーワード

解説

問題 (opens in a new tab)

いもす法の典型問題.

左下と右上を +1+1 , 左上と右下を 1-1 .
その後, それぞれの方向に累積和.

提出コード

func main() {
	N := readInt()
 
	grid := make([][]int, 1001)
	for i := 0; i < 1001; i++ {
		grid[i] = make([]int, 1001)
	}
 
	for i := 0; i < N; i++ {
		var lx, ly, rx, ry int
		scanIntVariables(&lx, &ly, &rx, &ry)
		grid[ly][lx] += 1
		grid[ry][rx] += 1
		grid[ry][lx] -= 1
		grid[ly][rx] -= 1
	}
 
	for y := 0; y <= 1000; y++ {
		for x := 1; x <= 1000; x++ {
			grid[y][x] += grid[y][x-1]
		}
	}
 
	for x := 0; x <= 1000; x++ {
		for y := 1; y <= 1000; y++ {
			grid[y][x] += grid[y-1][x]
		}
	}
 
	ans := map[int]int{}
	for y := 0; y <= 1000; y++ {
		for x := 0; x <= 1000; x++ {
			ans[grid[y][x]] += 1
		}
	}
 
	for i := 1; i <= N; i++ {
		writeLine(ans[i])
	}
}