TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1143
  • 题目
  • P1143(校内赛三)校门外的树2.0
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    NK中学校大门外有一条长度为L的笔直马路。在这条路的人行道上种有棵树。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上有L+1个整数点,即0,1,2,……,L,有的点上可能种有一棵树,每个点上最多只有一棵树。
    该地区的市政部门经常把人行道挖烂了再铺好,铺好了再挖烂。所以有的树在一年时间内会被反复挖倒很多次(每次施工结束时会再次把树栽好)。去年市政部门总共施工了M次,现在告诉你每次施工的起始点和终止点。问,这条路上哪些树被挖倒的次数最多。

    输入格式

    第一行有三个空格间隔的整数L、N和 M ,L代表马路的长度,N代表树的总数,M代表施工的次数。
    接下来一行有N个空格间隔的整数,表示每棵树所在的位置。
    接下来的M行每行包含两个整数,用一个空格隔开,表示一次施工的起始点和终止点的坐标。

    输出格式

    共一行,包含若干个空格间隔整数(由小到大排列),表示被挖倒次数最多的树的位置。

    样例输入

    500 5 3
    190 3 10 175 220
    150 300
    100 200
    170 471

    样例输出

    175 190

    提示

    位于3和10位置的树一次也没被挖倒
    位于175和190位置的树被挖到了3次
    位于220位置的树被挖倒了2次
    所以答案是175和190
    【数据范围】
    0<=L<=1000000000
    1<=N<=1000
    0<=M<=1000
    数据保证至少有一棵树会被挖倒