UOJ Logo

NOI.AC

#42. queen

统计

在一个n * n的棋盘上,放有m个皇后,其中每一个皇后都可以向上、下、左、右、左上、左下、右上、右下这8个方向移动(就是可以沿对角线和水平竖直方向移动)。其中每一个皇后可以攻击这八个方向上离它最近的皇后。

我们现在考虑每一个皇后会被从几个方向攻击到,设为w。很显然w属于[0,8]。最后要求出来t[0],t[1]……t[8]九个数,表示有多少皇后被攻击到0次,1次……8次。 数据保证m个皇后中任意两个不在同一个位置。

【输入格式】

第一行两个正整数n,m(n,m<=10^5),然后接下来m行,每一行x[i],y[i]分别表示第i个皇后的横坐标和纵坐标。(1<=x[i],y[i]<=n)

【输出格式】

一行9个整数,分别为t[0],t[1]……t[8],两个数中间用空格隔开。

【样例输入1】

8 4
4 3
4 8
6 5
1 6

【样例输出1】

0 3 0 1 0 0 0 0 0

【样例解释1】

皇后1能被皇后2攻击到(同一行),能被皇后3攻击到(同一对角线),能被皇后4攻击到(同一对角线)。
皇后2能被皇后1攻击到(同一行)。
皇后3能被皇后1攻击到(同对角线)。
皇后4能被皇后1攻击到(同对角线)。

【样例输入2】

10 3
1 1
1 2
1 3

【样例输出2】

0 2 1 0 0 0 0 0 0

【数据范围】

对于 30%的数据,n,m<=1000。

对于 60%的数据,n<=100000,m<=1000。

对于 100%的数据,n,m<=100000,1<=x[i],y[i]<=n。

(保证数据有梯度)