Comfortable Cows

题目描述

农夫约翰的牧场可以看作一个由正方形“格子”组成的巨大二维网格（可以想象成一张巨大的棋盘）。最开始时，牧场是空的。

农夫约翰将依次向牧场中加入 $N$（$1\le N\le 10^5$）头奶牛。第 $i$ 头奶牛会占据一个格子 $(x_i,y_i)$，且该格子与所有其他奶牛所占据的格子都不同（$0\le x_i,y_i\le 1000$）。

如果一头奶牛在水平方向或竖直方向上与恰好三头其他奶牛相邻，则称这头奶牛是“舒适的”。农夫约翰希望统计农场中舒适奶牛的数量。对于 $i$ 在 $1 \ldots N$ 的每个取值，输出加入第 $i$ 头奶牛后牧场中舒适奶牛的总数。

输入格式

第一行包含一个整数 $N$。 接下来的 $N$ 行每行包含两个用空格分隔的整数，表示一头奶牛所在格子的坐标 $(x,y)$。保证所有这些格子互不相同。

输出格式

输出共 $N$ 行。 第 $i$ 行应输出加入前 $i$ 头奶牛后，舒适奶牛的总数。

8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2

0
0
0
1
0
0
1
2

提示

加入前四头奶牛后，位于 $(1,1)$ 的奶牛是舒适的。 加入前七头奶牛后，位于 $(2,1)$ 的奶牛是舒适的。 加入前八头奶牛后，位于 $(2,1)$ 和 $(2,2)$ 的奶牛是舒适的。

SCORING: 测试点 1-4 满足 $N\le 400$。 测试点 5-12 没有额外限制。 题目来源（credits）：Benjamin Qi

标签: USACO|2021|Bronze

来源

USACO|2021|Bronze