分数: 300 分
问题陈述
Takahashi 从事体育分析工作。在某场比赛中, N 选手参加并比赛超过 T 回合。让 S_{j,i} 表示玩家的分数 i (1 \leq i \leq N) 回合 j (1 \leq j \leq T).
Takahashi 希望确定某个玩家以压倒性优势胜过其他玩家的回合。具体来说,他对某一轮比赛中“杰出”的球员的定义如下:
> 全面 j,让 M_{j,i} 是除玩家之外的所有玩家中的最高分数 i。如果 S_{j,i} \geq 2 \times M_{j,i} 成立,然后玩家 i 据说在回合中“杰出” j.
由于所有分数至少为 1,如果玩家 i 在回合中表现出色 j,那么 S_{j,i} 是该轮的最高分数,其他所有玩家的分数最多是它的一半。因此,有 最多 1 个 任何单轮比赛中都表现出色的选手。
确定轮数,超出 T 轮,其中存在杰出玩家。
约束
- 2 \leq N \leq 10^5
- 1 \leq T \leq 10^5
- N \times T \leq 10^6
- 1 \leq S_{j,i} \leq 10^9
- 所有输入值均为整数
输入
N T
S_{1,1} S_{1,2} \ldots S_{1,N}
S_{2,1} S_{2,2} \ldots S_{2,N}
\vdots
S_{T,1} S_{T,2} \ldots S_{T,N}
- 第一行包含玩家数量 N 和回合数 T,用空格分隔。
- 以下 T 行,其中 j- 第行 (1 \leq j \leq T) 包含分数 S_{j,1}, S_{j,2}, \ldots, S_{j,N} 玩家 1, 2, \ldots, N 回合 j,以空格分隔。
输出
在一行中打印轮数 T 轮,其中存在杰出玩家。
示例输入 1
3 4 10 3 4 5 6 5 1 1 3 7 4 4
示例输出 1
2
示例输入 2
3 3 5 6 5 10 8 9 100 99 100
示例输出 2
0
示例输入 3
5 6 100 200 50 30 40 90 80 85 88 91 1 1 1 1 1000000000 50 100 51 49 48 3 3 3 3 7 10 10 10 10 20
示例输出 3
4
示例输入 4
10 8 5 3 2 1 1 1 1 1 1 1 100 100 50 40 30 20 10 5 3 1 1000 400 499 500 200 100 50 25 12 6 7 7 7 7 7 7 7 7 7 14 999999999 500000000 1 1 1 1 1 1 1 1 1000000000 500000000 499999999 1 1 1 1 1 1 1 12 6 6 6 6 6 6 6 6 6 50 26 25 24 23 22 21 20 19 18
示例输出 4
4
示例输入 5
2 1 2 1
示例输出 5
1