← 返回比赛
已结束 GESP欢乐赛#60
← 上一题 下一题 →

A6064 | 领地计算

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

动物们靠自己的气息来划分领地，并且动物们有着强烈的领地意识，因此每天清晨动物园里的动物都会重新安排一下今天的领地分配，不同的是，动物园里的动物按照自己所属的势力来释放气息划分领地。

动物园是一个 $n \times n$ 的一个二维方阵， 现在一共有 $m$ 只动物， 其中第 $i$ 只动物现在的位置是处于 $(x_i, y_i)$, 并且会对以该点为中心, 边长为 $d_i$ 的正方形区域释放一份属于自己势力的气息。该动物所属的势力为 $t_i$ , $t_i = 0$ 时代表狮子帮， $t_i = 1$ 时候代表老虎帮。

一个位置最终属于哪一方取决于哪一方在此处释放的气息更多，如果一个坐标双方势力释放的气息一样多，则该位置属于无主之地。请问今天狮子帮和老虎帮的领地分别占据了几个位置？

输入格式

第一行输入两个整数 $n, m$, 分别代表动物园的大小， 动物的数量。

接下来 $m$ 行每行 $4$ 个数字 $x_{i}, y_{i}, d_{i}, t_{i}$,代表该动物所处的坐标,释放气息的正方形规模大小以及所属的势力。 $(1 \le x_{i}, y_{i}, d_{i}\le n,m \le 500,d_{i}$是奇数，$0 \le t_{i} \le 1)$。

输出格式

输出两个整数，使用空格隔开， 分别代表今日狮子帮的领地数量和老虎帮的领地数量。

输入输出样例

输入 #1
4 4
2 3 3 0
4 1 3 1
1 2 1 0
2 4 1 1
输出 #1
7 3
C++ 编辑器
输入
输出