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

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

题目描述

现在有一块很大的草原,这个草原分成了 nnmm 列。 在这块草原的天空中,飘着 kk 个气球。第 ii 个气球,位置在第 xix_i 行第 yiy_i 列上空,距离地面高度 hih_i,气球的颜色为 cic_i

从一个位置向上看,只能看到这个位置正上方的,距离地面最近的气球。小明想知道,从每个位置向上看,能看到的气球的颜色分别是什么。如果这个位置上空没有气球,则输出 00

输入格式

第一行,包括三个整数 n,m,kn,m,k,表示草原大小为 nnmm 列,天空中有 kk 个气球。

接下来的 kk 行,每行包括四个整数:xi,yi,hi,cix_i,y_i,h_i,c_i,表示第 ii 个气球,位置在第 xix_i 行第 yiy_i 列上空,距离地面高度 hih_i,气球的颜色为 cic_i

输出格式

共包含 nn 行,每行 mm 个数字。其中第 ii 行第 jj 个数字表示从这个位置向上看能看到的气球的颜色。如果这个位置上空没有气球,则输出 00

2 2 5
2 1 4 4
1 2 8 9
1 2 9 4
1 1 8 3
2 1 9 3

3 9
4 0

3 3 5
1 1 6 7
2 2 7 5
3 1 8 3
2 2 6 1
2 1 3 4

7 0 0
4 1 0
3 0 0

提示

样例 1 解释

  • 第一行第一列上空只有一个气球,颜色为 33
  • 第一行第二列上空高度最低的气球高度为 88,颜色为 99
  • 第二行第一列上空高度最低的气球高度为 44,颜色为 44
  • 第二行第二列上空没有气球。

数据规模与约定

对于 100%100\% 的数据,1n,m1031 \leq n, m \leq 10^31k1051 \leq k \leq 10^51hi,ci1091 \leq h_i, c_i \leq 10^9。保证不存在两个气球的位置(xi,yi,hix_i, y_i, h_i)完全相同。

测试点编号 n,mn, m kk hih_i cic_i 特殊性质
11 =2= 2 10\leq 10 10\leq 10
2,32, 3 10 \leq 10 200\leq 200
44 =1= 1 105\leq 10^5 109\leq 10^9 109\leq 10^9
55 300\leq 300 9×104\leq 9 \times 10^4 每一个位置上空恰好有一个气球
66 1000\leq 1000 105\leq 10^5 每一个位置上空至多有一个气球
77 =1= 1
8108 \sim 10 109\leq 10^9