레이팅 미적용농부 존(Farmer John)은 정육면체 모양의 치즈 덩어리를 가지고 있다. 이 치즈는 3차원 좌표 공간에서 \((0,0,0)\)부터 \((N, N, N)\)까지 놓여 있다 (\(2 \leq N \leq 1000\)). 농부 존은 치즈 덩어리에 \(Q\)번 (\(1 \leq Q \leq 2 \cdot 10^5\))의 갱신 연산을 수행할 것이다.
각 갱신 연산에서 FJ는 정수 좌표 \((x, y, z)\)부터 \((x+1, y+1, z+1)\)까지의 \(1\) x \(1\) x \(1\) 치즈 블록을 파낸다. 여기서 \(0\le x,y,z
각 갱신 후, FJ가 \(1\) x \(1\) x \(N\) 크기의 벽돌을 치즈 덩어리 안에 남은 치즈와 전혀 겹치지 않게 끼워 넣을 수 있는 서로 다른 배치의 수를 출력하시오. 벽돌의 모든 꼭짓점은 세 축 모두에서 \([0,N]\) 범위의 정수 좌표를 가져야 한다. FJ는 벽돌을 원하는 대로 회전할 수 있다.
문제 제공: Chongtian Ma, Alex Liang
배점
- 입력 2-4: \(N\le 10\), \(Q \le 1000\)
- 입력 5-7: \(N\le 100\), \(Q \le 1000\)
- 입력 8-16: 추가 제약이 없다
문제 제공: Chongtian Ma, Alex Liang
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에는 파낼 좌표 \(x\), \(y\), \(z\)가 주어진다.
각 갱신 연산 후, 배치의 수를 나타내는 정수를 출력한다.
2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 00
0
1
2
5After the first three updates, the \(1\times 2 \times 1\) brick spanning
\([0, 1]\times [0, 2]\times [0, 1]\) does not overlap with the remaining cheese,
so it contributes toward the answer.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Bronze