B - Outstanding Score Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はスポーツ分析の仕事をしています。ある大会では N 人の選手が参加しており、T ラウンドにわたって競技が行われました。ラウンド j（1 \leq j \leq T）における選手 i（1 \leq i \leq N）の得点を S_{j,i} とします。

高橋君は、ある選手が他の選手を圧倒的に上回ったラウンドを特定したいと考えています。具体的には、あるラウンドにおいて選手が「ずば抜けている」ことを次のように定義しました：

> ラウンド j において、選手 i 以外のすべての選手の得点の最大値を M_{j,i} とする。S_{j,i} \geq 2 \times M_{j,i} が成り立つとき、選手 i はラウンド j で「ずば抜けている」とする。

なお、すべての得点は 1 以上であるため、もし選手 i がラウンド j でずば抜けているならば、S_{j,i} はそのラウンドの最大得点であり、かつ他のどの選手の得点もその半分以下です。したがって、1 つのラウンドでずば抜けている選手は 高々 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}
  • 1 行目には、選手の数 N とラウンドの回数 T が空白区切りで与えられる。
  • 続く T 行のうち j 行目（1 \leq j \leq T）には、ラウンド j における選手 1, 2, \ldots, N の得点 S_{j,1}, S_{j,2}, \ldots, S_{j,N} が空白区切りで与えられる。

出力

T ラウンドのうち、ずば抜けている選手が存在するラウンドの数を 1 行で出力せよ。

入力例 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

Score : 300 pts

Problem Statement

Takahashi works in sports analytics. In a certain tournament, N players participated and competed over T rounds. Let S_{j,i} denote the score of player i (1 \leq i \leq N) in round j (1 \leq j \leq T).

Takahashi wants to identify rounds where a certain player overwhelmingly outperformed the others. Specifically, he defined a player being "outstanding" in a round as follows:

> In round j, let M_{j,i} be the maximum score among all players other than player i. If S_{j,i} \geq 2 \times M_{j,i} holds, then player i is said to be "outstanding" in round j.

Since all scores are at least 1, if player i is outstanding in round j, then S_{j,i} is the maximum score in that round, and every other player's score is at most half of it. Therefore, there is at most one outstanding player in any single round.

Determine the number of rounds, out of the T rounds, in which an outstanding player exists.

Constraints

  • 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
  • All input values are integers

Input

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}
  • The first line contains the number of players N and the number of rounds T, separated by a space.
  • The following T lines, where the j-th line (1 \leq j \leq T) contains the scores S_{j,1}, S_{j,2}, \ldots, S_{j,N} of players 1, 2, \ldots, N in round j, separated by spaces.

Output

Print in one line the number of rounds, out of the T rounds, in which an outstanding player exists.

Sample Input 1

3 4
10 3 4
5 6 5
1 1 3
7 4 4

Sample Output 1

2

Sample Input 2

3 3
5 6 5
10 8 9
100 99 100

Sample Output 2

0

Sample Input 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

Sample Output 3

4

Sample Input 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

Sample Output 4

4

Sample Input 5

2 1
2 1

Sample Output 5

1