No.709 優勝可能性

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 50
作問者 : ei1333ei1333 / テスター : LuzhiledLuzhiled

2 ProblemId : 1990 / 出題時の順位表

問題文

$N$ 人がいて $1$ から $N$ までの番号が振られています。 すべての人は $M$ 種類の能力パラメータを持っていて, 人 $i$ の能力 $j$ のパラメータは $R_{i,j}$ です。

これから計 $N$ 回プログラミングコンテストが開かれます。 $k$ 回目のコンテストでは, 人 $1$ から人 $k$ までの $k$ 人が参加します。

それぞれのコンテストについて優勝できる可能性がある人は $1$ 種類以上の能力パラメータにおいて参加者のうちの最大値をとる人に限ります。 それぞれのコンテストで, 何人が優勝できる可能性があるか調べてください。

入力

$N$ $M$
$R_{1,1}$ $R_{1,2}$ ... $R_{1,M}$
$R_{2,1}$ $R_{2,2}$ ... $R_{2,M}$
:
$R_{N,1}$ $R_{N,2}$ ... $R_{N,M}$

$1$ 行目に, 人数 $N(1 \le N \le 10^5)$ と能力パラメータの種類数 $M(1 \le M \le 10)$ が与えられます。

つづく $N$ 行のうち $i$ 行目には $M$ 個の整数 $R_{i,j}(1 \le R_{i,j} \le 10^9)$ が空白区切りで与えられ, $j$ 番目の値は人 $i$ の能力 $j$ のパラメータを意味します。

出力

出力は $N$ 行からなります。$i$ 行目には $i$ 回目のコンテストで優勝できる可能性がある人数を出力してください。

サンプル

サンプル1
入力
5 1
5
4
5
6
7
出力
1
1
2
1
1
  • $1, 2$ 回目のコンテストでは人 $1$ が必ず優勝します。
  • $3$ 回目のコンテストでは人 $1, 3$ に優勝可能性があります。ともに能力 $1$ のパラメータが $5$ で最大値をとります。
  • $4$ 回目のコンテストでは人 $4$ が必ず優勝します。
  • $5$ 回目のコンテストでは人 $5$ が必ず優勝します。
サンプル2
入力
7 3
1 2 3
3 1 2
1 2 1
3 3 4
1000000000 1000000000 1000000000
334 57 119
114 1333 514
出力
1
2
3
2
1
1
1
  • $1$ 回目のコンテストでは人 $1$ が必ず優勝します。
  • $2$ 回目のコンテストでは人 $1, 2$ に優勝可能性があります。 人 $1$ は能力 $2, 3$, 人 $2$ は能力 $1$ について最大値をとります。
  • $3$ 回目のコンテストでは人 $1, 2, 3$ に優勝可能性があります。 人 $1$ は能力 $2, 3$, 人 $2$ は能力 $1$, 人 $3$ は能力 $2$ について最大値をとります。
  • $4$ 回目のコンテストでは人 $2, 4$ に優勝可能性があります。 人 $2$ は能力 $1$, 人 $4$ は能力 $1, 2, 3$ について最大値をとります。
  • $5$ 回目のコンテスト以降では人 $4$ が必ず優勝します。
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。