页面无法加载？点击这里可能会修复。
Placeholder

#8177
子任务

치즈 블록 1s 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分

추가 제약 조건 없음


示例 

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0
0
0
1
2
5

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


来源

USACO 2024 December Bronze

需要登录才能编写代码。