{"problem":{"name":"C. Tournament","description":{"content":"Recently a tournament in _k_ kinds of sports has begun in Berland. Vasya wants to make money on the bets. The scheme of the tournament is very mysterious and not fully disclosed. Competitions are hel","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF878C"},"statements":[{"statement_type":"Markdown","content":"Recently a tournament in _k_ kinds of sports has begun in Berland. Vasya wants to make money on the bets.\n\nThe scheme of the tournament is very mysterious and not fully disclosed. Competitions are held back to back, each of them involves two sportsmen who have not left the tournament yet. Each match can be held in any of the _k_ kinds of sport. Loser leaves the tournament. The last remaining sportsman becomes the winner. Apart of this, the scheme can be arbitrary, it is not disclosed in advance.\n\nVasya knows powers of sportsmen in each kind of sport. He believes that the sportsmen with higher power always wins.\n\nThe tournament is held every year, and each year one new participant joins it. In the first tournament, only one sportsman has participated, in the second there were two sportsmen, and so on. Vasya has been watching the tournament for the last _n_ years. Help him to find the number of possible winners for each of the _n_ tournaments.\n\n## Input\n\nThe first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 5·104, 1 ≤ _k_ ≤ 10) — the number of tournaments and the number of kinds of sport, respectively.\n\nEach of the next _n_ lines contains _k_ integers _s__i_1, _s__i_2, ..., _s__ik_ (1 ≤ _s__ij_ ≤ 109), where _s__ij_ is the power of the _i_\\-th sportsman in the _j_\\-th kind of sport. The sportsman with higher powers always wins. It's guaranteed that for any kind of sport all of these powers are distinct.\n\n## Output\n\nFor each of the _n_ tournaments output the number of contenders who can win.\n\n[samples]\n\n## Note\n\nIn the first sample:\n\nIn the first tournament there is only one sportsman, and he is the winner.\n\nIn the second tournament, there are two sportsmen, and everyone can defeat another, depending on kind of sports.\n\nIn the third tournament, the third sportsman in the strongest in both kinds of sports, so he is the winner regardless of the scheme.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"最近，Berland 举办了一场涉及 #cf_span[k] 种运动的锦标赛。Vasya 希望通过下注赚钱。\n\n锦标赛的赛制非常神秘，尚未完全公开。比赛依次进行，每场涉及两名尚未被淘汰的运动员。每场比赛可以在任意一种 #cf_span[k] 种运动中进行。失败者被淘汰，最后剩下的运动员成为冠军。此外，赛制可以是任意的，事先并不公开。\n\nVasya 知道每位运动员在每种运动中的实力。他相信实力更高的运动员总是获胜。\n\n锦标赛每年举办一次，每年会新增一名参赛者。第一届锦标赛只有 1 名运动员参加，第二届有 2 名，依此类推。Vasya 已经观看了过去 #cf_span[n] 年的锦标赛。请帮助他计算每届锦标赛中可能的冠军人数。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 5·104], #cf_span[1 ≤ k ≤ 10]) —— 分别表示锦标赛的届数和运动种类数。\n\n接下来的 #cf_span[n] 行，每行包含 #cf_span[k] 个整数 #cf_span[si1, si2, ..., sik] (#cf_span[1 ≤ sij ≤ 109])，其中 #cf_span[sij] 表示第 #cf_span[i] 位运动员在第 #cf_span[j] 种运动中的实力。实力更高的运动员总是获胜。保证对于任意一种运动，所有实力值互不相同。\n\n对于每届 #cf_span[n] 个锦标赛，请输出可能成为冠军的运动员人数。\n\n在第一个样例中：\n\n第一屆锦标赛只有一名运动员，他就是冠军。\n\n第二屆锦标赛有两名运动员，他们各自在某种运动中都能击败对方，具体结果取决于比赛安排的运动类型。\n\n第三屆锦标赛中，第三位运动员在两种运动中实力均最强，因此无论赛制如何，他都是冠军。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 5·104], #cf_span[1 ≤ k ≤ 10]) —— 分别表示锦标赛的届数和运动种类数。接下来的 #cf_span[n] 行，每行包含 #cf_span[k] 个整数 #cf_span[si1, si2, ..., sik] (#cf_span[1 ≤ sij ≤ 109])，其中 #cf_span[sij] 表示第 #cf_span[i] 位运动员在第 #cf_span[j] 种运动中的实力。实力更高的运动员总是获胜。保证对于任意一种运动，所有实力值互不相同。\n\n## Output\n\n对于每届 #cf_span[n] 个锦标赛，请输出可能成为冠军的运动员人数。\n\n[samples]\n\n## Note\n\n在第一个样例中：\n\n第一屆锦标赛只有一名运动员，他就是冠军。\n\n第二屆锦标赛有两名运动员，他们各自在某种运动中都能击败对方，具体结果取决于比赛安排的运动类型。\n\n第三屆锦标赛中，第三位运动员在两种运动中实力均最强，因此无论赛制如何，他都是冠军。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**\n\n*   Let $n, k \\in \\mathbb{Z}^+$ denote the number of tournaments and the number of sports, respectively.\n*   Let $J = \\{1, 2, \\dots, k\\}$ be the set of sports.\n*   Let $S$ be an $n \\times k$ matrix of integers, where $S_{i,j}$ represents the power of the $i$-th participant in the $j$-th sport.\n*   For any integer $t \\in \\{1, \\dots, n\\}$, let $V_t = \\{1, 2, \\dots, t\\}$ be the set of participants in the $t$-th tournament.\n*   Let $D_t = (V_t, E_t)$ be a directed graph representing the dominance capabilities in the $t$-th tournament, defined as follows:\n    $$E_t = \\{(u, v) \\in V_t \\times V_t \\mid u \\neq v \\land \\exists j \\in J, S_{u,j} > S_{v,j}\\}$$\n\n**Constraints**\n\n*   $1 \\le n \\le 5 \\cdot 10^4$\n*   $1 \\le k \\le 10$\n*   $1 \\le S_{i,j} \\le 10^9$ for all $i, j$.\n*   For any fixed sport $j \\in J$, all powers are distinct: $\\forall u, v \\in \\{1, \\dots, n\\}, u \\neq v \\implies S_{u,j} \\neq S_{v,j}$.\n*   (Note: The distinctness constraint implies that for any pair $u, v$, either $(u, v) \\in E_t$ or $(v, u) \\in E_t$, or both. Thus, $D_t$ is a semicomplete graph.)\n\n**Objective**\n\nFor each $t \\in \\{1, \\dots, n\\}$, calculate the cardinality of the set of possible winners $W_t$, defined as the set of vertices in $V_t$ that can reach all other vertices in $D_t$:\n\n$$|W_t| \\quad \\text{where} \\quad W_t = \\{u \\in V_t \\mid \\forall v \\in V_t \\setminus \\{u\\}, \\text{ there exists a path from } u \\text{ to } v \\text{ in } D_t\\}$$\n\nOutput the sequence $|W_1|, |W_2|, \\dots, |W_n|$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF878C","tags":["data structures","graphs"],"sample_group":[["3 2\n1 5\n5 1\n10 10","1\n2\n1"],["3 2\n2 2\n3 3\n1 10","1\n1\n3"],["3 2\n2 3\n1 1\n3 2","1\n1\n2"]],"created_at":"2026-03-03 11:00:39"}}