← 返回题目列表

AtCoder · awc0031_b

B. 优秀分数

中文机器翻译题面 查看原题

分数: 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