[语言月赛 202404] 天上的气球

Luogu

IDLGB3964

Time1000ms

Memory512MB

DifficultyP2

2024O2优化数组语言月赛

现在有一块很大的草原，这个草原分成了 $n$ 行 $m$ 列。在这块草原的天空中，飘着 $k$ 个气球。第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。从一个位置向上看，只能看到这个位置正上方的，距离地面最近的气球。小明想知道，从每个位置向上看，能看到的气球的颜色分别是什么。如果这个位置上空没有气球，则输出 $0$。 ## Input 第一行，包括三个整数 $n,m,k$，表示草原大小为 $n$ 行 $m$ 列，天空中有 $k$ 个气球。接下来的 $k$ 行，每行包括四个整数：$x_i,y_i,h_i,c_i$，表示第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。 ## Output 共包含 $n$ 行，每行 $m$ 个数字。其中第 $i$ 行第 $j$ 个数字表示从这个位置向上看能看到的气球的颜色。如果这个位置上空没有气球，则输出 $0$。 [samples] ## Note ### 样例 1 解释 - 第一行第一列上空只有一个气球，颜色为 $3$； - 第一行第二列上空高度最低的气球高度为 $8$，颜色为 $9$； - 第二行第一列上空高度最低的气球高度为 $4$，颜色为 $4$； - 第二行第二列上空没有气球。 ### 数据规模与约定对于 $100\%$ 的数据，$1 \leq n, m \leq 10^3$，$1 \leq k \leq 10^5$，$1 \leq h_i, c_i \leq 10^9$。保证不存在两个气球的位置（$x_i, y_i, h_i$）完全相同。 | 测试点编号 | $n, m$ | $k$ | $h_i$ | $c_i$ | 特殊性质 | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $= 2$ | $\leq 10$ | $\leq 10$ | $\leq 10$ | 无 | | $2, 3$ | $ \leq 10$ | $\leq 200$ | $\leq 10$ | $\leq 10$ | 无 | | $4$ | $= 1$ | $\leq 10^5$ | $\leq 10^9$ | $\leq 10^9$ | 无 | | $5$ | $\leq 300$ | $\leq 9 \times 10^4$ | $\leq 10^9$ | $\leq 10^9$ | 每一个位置上空**恰好**有一个气球 | | $6$ | $\leq 1000$ | $\leq 10^5$ | $\leq 10^9$ | $\leq 10^9$ | 每一个位置上空**至多**有一个气球 | | $7$ | $\leq 1000$ | $\leq 10^5$ | $\leq 10^9$ | $= 1$ | 无 | | $8 \sim 10$ | $\leq 1000$ | $\leq 10^5$ | $\leq 10^9$ | $\leq 10^9$ | 无 |

Samples

Input #1

Output #1

3 9
4 0

Input #2

Output #2

7 0 0
4 1 0
3 0 0

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202404] 天上的气球",
    "description": {
      "content": "现在有一块很大的草原，这个草原分成了 $n$ 行 $m$ 列。 在这块草原的天空中，飘着 $k$ 个气球。第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。 从一个位置向上看，只能看到这个位置正上方的，距离地面最近的气球。小明想知道，从每个位置向上看，能看到的气球的颜色分别是什么。如果这个位置上空没有气球，则输出 $0$。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3964"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "现在有一块很大的草原，这个草原分成了 $n$ 行 $m$ 列。\n在这块草原的天空中，飘着 $k$ 个气球。第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。\n\n从一个位置向上看，只能看到这个位置正上方的，距离地面最近的气球。小明想知道，从每个位置向上看，能看到的气球的颜色分别是什么。如果这个位置上空没有气球，则输出 $0$。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments