[语言月赛 202312] 颜料覆盖

Luogu

IDLGB3909

Time1000ms

Memory512MB

DifficultyP1

2023O2优化循环结构语言月赛

给定一个 $n$ 行 $m$ 列的矩阵 $a$。每一行代表画作的一块区域。每一行从前往后分别代表 $m$ 次绘画。用 $a _ {i, j}$ 代表序列中第 $i$ 行第 $j$ 列的元素，$a _ {i, j}$ 代表区域 $i$ 在第 $j$ 次绘画中被涂抹的颜料强度。如果 $a _ {i, j} = 0$，那么代表区域 $i$ 在第 $j$ 次中未被涂抹。现在，对于每个区域，你需要找出涂抹强度最大的一次是哪一次。同时，你需要找出，在这一次之前，有多少次涂抹（不计算未涂抹的情况）强度比这一次小。保证对于某个区域，不会出现两次涂抹强度相同且最大。 ## Input 输入共 $n + 1$ 行。第一行为两个整数 $n, m$，分别代表区域数和绘画次数。接下来 $n$ 行，每行 $m$ 个整数，代表矩阵 $a$。 ## Output 输出共 $n$ 行，每行两个整数，分别代表涂抹强度最大的一次是哪一次，和在这一次之前，有多少次涂抹（不计算未涂抹的情况）强度比这一次小。 [samples] ## Background 一副精美的画作可能需要很多次重复的颜料涂抹。涂抹的一层层颜料会产生许多覆盖。这一次我们将这一个情景简化后交给了你，希望你能够解开颜料覆盖的奥秘。 ## Note ### 样例 1 解释 - 第一行（第一个区域）中，第 $\color{red}4$ 次涂抹的强度最大，为 $3$。在第 $4$ 次之前，有且仅有第 $2$ 次这一次「有涂抹（不为 $0$）」且「强度比第 $4$ 次小」，故答案为 `4 1`。 - 第二行（第二个区域）中，第 $\color{red}3$ 次涂抹的强度最大，为 $1$。在第 $3$ 次之前，该区域没有被涂抹过（即第 $3$ 次之前全为 $0$），故答案为 `3 0`。 - 第三行（第三个区域）中，第 $\color{red}5$ 次涂抹的强度最大，为 $5$。在第 $5$ 次之前，有 $\color{red}4$ 次「有涂抹」且「强度比第 $5$ 次小」，因此答案为 `5 4`。 ### 数据规模与约定对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10 ^ 6$，$1 \leq n \times m \leq 10 ^ 6$，$0 \leq a _ {i, j} \leq 10 ^ 9$。 | 测试点 | $n$ | $m$ | 特殊性质 | | :-: | :-: | :-: | :-: | | $1$ | $= 1$ | $= 1$ | 无 | | $2 \sim 3$ | $\leq 10$ | $\leq 10$ | 无 | | $4 \sim 6$ | $\leq 10 ^ 3$ | $\leq 10 ^ 3$ | 无 | | $7 $ | $\leq 1$ | $\leq 10 ^ 6$ | 无 | | $8$ | $\leq 10 ^ 6$ | $\leq 1$ | 无 | | $9 \sim 10$ | $\leq 10 ^ 6$ | $\leq 10 ^ 6$ | 每一行的第一个元素是这一行的最大值 | | $11 \sim 12$ | $\leq 10 ^ 6$ | $\leq 10 ^ 6$ | 每一行的最后一个元素是这一行的最大值 | | $13 \sim 14$ | $\leq 10 ^ 6$ | $\leq 10 ^ 6$ | 每一行有且仅有一个非 $0$ 元素 | | $15 \sim 20$ | $\leq 10 ^ 6$ | $\leq 10 ^ 6$ | 无 | 保证在矩阵的某一行中不存在两个元素相同且最大，保证不存在某一行全部为 $0$。

Samples

Input #1

Output #1

4 1
3 0
5 4

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202312] 颜料覆盖",
    "description": {
      "content": "给定一个 $n$ 行 $m$ 列的矩阵 $a$。每一行代表画作的一块区域。每一行从前往后分别代表 $m$ 次绘画。 用 $a _ {i, j}$ 代表序列中第 $i$ 行第 $j$ 列的元素，$a _ {i, j}$ 代表区域 $i$ 在第 $j$ 次绘画中被涂抹的颜料强度。如果 $a _ {i, j} = 0$，那么代表区域 $i$ 在第 $j$ 次中未被涂抹。 现在，对于每个区域，你需要找",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3909"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 $n$ 行 $m$ 列的矩阵 $a$。每一行代表画作的一块区域。每一行从前往后分别代表 $m$ 次绘画。\n\n用 $a _ {i, j}$ 代表序列中第 $i$ 行第 $j$ 列的元素，$a _ {i, j}$ 代表区域 $i$ 在第 $j$ 次绘画中被涂抹的颜料强度。如果 $a _ {i, j} = 0$，那么代表区域 $i$ 在第 $j$ 次中未被涂抹。\n\n现在，对于每个区域，你需要找...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments