#PU1444. USACO 2024 December Contest, Bronze — Problem 2. Farmer John's Cheese Block

    ID: 1296 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases区间DP分治

USACO 2024 December Contest, Bronze — Problem 2. Farmer John's Cheese Block

USACO 2024 December Contest, Bronze — Problem 2. Farmer John's Cheese Block

题目描述

Farmer John has a block of cheese in the shape of a cube. It lies on the 3-dimensional coordinate plane, extending from (0,0,0)(0,0,0) to (N,N,N)(N, N, N) (2≤N≤10002 \leq N \leq 1000). Farmer John will perform a series of QQ (1≤Q≤2⋅1051 \leq Q \leq 2 \cdot 10^5) update operations to his cheese block. For each update operation, FJ will carve out the 11 by 11 by 11 block of cheese extending from integer coordinates (x,y,z)(x, y, z) to (x+1,y+1,z+1)(x+1, y+1, z+1), where 0≤x,y,z<N0\le x,y,z<N. It is guaranteed that there will exist a 11 by 11 by 11 block of cheese at the location FJ carves. Since FJ is playing Moocraft, gravity does not cause parts of the cheese to fall if cheese below is carved. After each update, output the number of distinct configurations that FJ can stick a 11 by 11 by NN brick in the cheese block such that no part of the brick overlaps with any remaining cheese. Every vertex of the brick must have integer coordinates in the range [0,N][0,N] for all three axes. FJ may rotate the brick however he wants.

输入格式

The first line contains NN and QQ. The following QQ lines contain xx, yy, and zz, the coordinates to be carved.

输出格式

After each update operation, output an integer, the number of configurations.

数据范围

Inputs 2-4: N≤10N\le 10 and Q≤1000Q \le 1000 Inputs 5-7: N≤100N\le 100 and Q≤1000Q \le 1000 Inputs 8-16: No additional Problem credits: Chongtian Ma, Alex Liang

样例

样例 1

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0
0
0
1
2
5
After 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.