페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8177
서브태스크

치즈 블록 1초 1024MB

문제

재민이는 게임 마인코레프트에서 정육면체 모양의 치즈 블록을 가지고 있다. 이 치즈 블록은 3차원 좌표 평면에 놓여 있으며, 좌표 (0,0,0)에서 (N,N,N)까지 확장된다.

재민이는 치즈 블록에 대해 Q번 업데이트 작업을 수행한다.

각 업데이트 작업에서, 재민이는 (x, y, z) 좌표에서 (x+1, y+1, z+1)까지 확장되는 1×1×1 크기의 치즈 블록을 깎는다. 이때, 재민이가 깎을 위치에는 반드시 1×1×1 크기의 치즈 블록이 존재한다고 보장된다. (마인코레프트에서는 치즈 아래가 깎여도 중력에 의해 치즈가 떨어지지 않는다)

각 업데이트 후, 재민이는 치즈가 깎여나간 위치에 1×1×N 크기의 벽돌을 치즈 블록에 겹치지 않도록 배치할 수 있는 서로 다른 경우의 수를 출력해야 한다. 벽돌의 모든 꼭짓점은 세 축에 대해 [0, N] 범위 내의 정수 좌표여야 한다. (재민이는 벽돌을 원하는 대로 회전시킬 수 있다)


입력

첫 번째 줄에 N과 Q가 주어진다. (2≤N≤1,000; 1≤Q≤2⋅10^5)

그 후 Q개의 줄에 걸쳐, 각 줄에 x, y, z 좌표가 주어진다. (0≤x, y, z<N)


출력

각 업데이트 작업 후, 벽돌을 배치할 수 있는 서로 다른 구성 수를 출력한다.


부분문제

번호 점수 조건
#120점

N≤10 ; Q≤1000

#230점

N≤100 ; Q≤1000

#350점

추가 제약 조건 없음


예제1

입력
25
000
111
010
100
110
출력
0
0
1
2
5

첫 세 번의 업데이트 후, 1×2×1 크기의 벽돌이 [0,1]×[0,2]×[0,1] 범위에 걸쳐 남아있는 치즈와 겹치지 않아서 답에 기여하게 된다.


출처

USACO 2024 December Bronze

역링크