← 返回题目列表

AtCoder · tkppc2015_f

F. 铜管乐队

中文机器翻译题面 查看原题

問題文

joisinoOnee-chan决定接下来去铜管乐队俱乐部。
Joisino Onee-chan产生了兴趣并去了音乐室,在那里她发现辅导老师遇到了麻烦。
Joisino Onee-chan 被期望成为一名优秀的程序员,并得到了老师的咨询。

咨询内容如下。

  • 在这个铜管乐队中 使用N仪器,每个仪器都有一个 分配的编号最大为1~N。乐器i(1≦i≦N)的玩家是i有人。 使用它可以使
  • 楽器i听起来优美。i人在舞台边i+1需要在等分的位置上均匀地排队。这样,N每个演奏乐器的人在舞台上排成一排。
  • 虽然不考虑人的宽度,但如果两个或两个以上的人站在完全相同的位置,则只有使用编号最低的乐器的人会站在该位置,而使用其他乐器的人将不被允许站在舞台上。
  • 这次铜管乐队比赛 有M名评委,每个评委 分配的编号最大为1~M。他们与舞台平行排列。
  • 審査員j(1≦j≦M)是舞台的水平长度。1从舞台的左边缘开始, 我的位置是P_j/Q_j 。
  • 每个裁判都有固定的距离。法官j应该是查看距离他一定距离内的玩家,玩家数量为 我知道是K_j。
  • 为了帮助练习,我想知道在他们观看的人中距离每个评委最远的人演奏的乐器的编号。
  • Joisino-neechan是一位优秀的程序员,她使用她当前知道的信息(乐器的数量)。N,评委人数M、審査員j位置P_j/Q_j,观看的玩家数量K_j),评委 我决定创建一个程序来查找j看到的玩家中距离最远的玩家所演奏的乐器的编号。

    如果有两个距离最远的玩家,不可能只看到其中一个。另外,输出两个演奏者中演奏数字较小的乐器的那个。 (如果相同则原样输出)


    入力

    输入是按以下格式从标准输入给出的。

    .
    N M
    P_1 Q_1 K_1
    P_2 Q_2 K_2
    :
    P_M Q_M K_M
    
    • 1行显示仪器的数量。N(1≦N≦3*10^4),评委人数M(1≦M≦30)用空格分隔。
    • 2从线M行j行中,判断 表示j位置的整数P_j(1≦P_j<Q_j) Q_j(2≦Q_j≦N+1) 可查看的玩家数量K_j用空格分隔。
    • 对于所有输入,评委数量不会多于表演者数量。

    配点

    针对此问题设置了部分分数。

  • 数据集1所以,N≦5000并且回答正确,15积分
  • 数据集2没有额外的限制,如果你回答正确, 打印105积分
  • 出力

    输出是 由M行组成。j行中,判断 表示j能看到的最远演奏者所演奏的乐器编号。
    另外,在输出末尾放置一个换行符。


    入力例1

    5 2
    3 5 3
    1 4 4
    

    出力例1

    1
    2
    
    • 在这种情况下,玩家在舞台上排列如下图所示。 (蓝线代表舞台边缘,数字代表持有该数字乐器的演奏者。)
      審査員1位于绿色箭头位置的绿色括号内3看着人。括号内最远的玩家是 作为1的玩家, 输出1。 我锻炼
      審査員2在红色箭头位置的红色括号内 使用4看着人。括号内最远的玩家是 作为2播放器5玩家,因此编号最小的玩家2。 我锻炼

    入力例2

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

    出力例2

    1
    5
    7
    4
    6
    
    • 在这种情况下,审查员4的观看范围超出了舞台边缘。