優勝可能性 [yukicoder No.709] - はまやんはまやんはまやん

解法

シミュレーションする。
以下の配列を用意して実装していく。
　
ma[i] := i番目の能力の最大値
win[i] := i番目の能力の最大値を持つ参加者の添字のベクタ
cnt[i] := i番目の参加者が何種類の能力の最大値を持っているか
　
1人目だけ処理を分けておこう。
最初なので、ma[i] = R[0][i], win[i] = {0}, cnt[0] = Mとなっているはずである。
　
参加者を次々処理して、答えを増減させることで高速に答えを求めていく。
ma[m] = R[i][m]であれば、ma[m]は変わらず、win[m]にiが追加されるだけ。
このときにcnt[m]も++されるが、初めて増えるなら答えも1つ増える。
　
ma[m] ＜ R[i][m]であれば、最大値が更新されるので、win[m]をクリアして、新しく作る。
win[m]のクリア時にcntを減らして、0になった要素があれば答えを1つ減らす。
クリア時の処理でTLEが起きそうなようにも見えるが、各参加者の各能力について
クリアの処理はちょうど1度だけ起きるので、ならすと全体でO(NM)なので、大丈夫。

int N, M, R[101010][10];
int ma[10];
vector<int> win[10];
int cnt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) rep(m, 0, M) cin >> R[i][m];

    rep(m, 0, M) ma[m] = R[0][m];
    rep(m, 0, M) win[m].push_back(0);
    cnt[0] = M;
    printf("1\n");

    int ans = 1;
    rep(i, 1, N) {
        rep(m, 0, M) {
            if (ma[m] == R[i][m]) {
                win[m].push_back(i);
                cnt[i]++;
                if (cnt[i] == 1) ans++;
            }
            else if (ma[m] < R[i][m]) {
                fore(j, win[m]) {
                    cnt[j]--;
                    if (cnt[j] == 0) ans--;
                }
                win[m].clear();

                ma[m] = R[i][m];
                win[m].push_back(i);
                cnt[i]++;
                if (cnt[i] == 1) ans++;
            }
        }

        printf("%d\n", ans);
    }
}