P3407 散步

    • 104通过
    • 505提交
  • 题目提供者 kkksc03 站长团
  • 评测方式 云端评测
  • 标签 枚举,暴力 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    一条道路上,位置点用整数A表示。

    当A=0时,有一个王宫。当A>0,就是离王宫的东边有A米,当A<0,就是离王宫的西边有A米。

    道路上,有N个住宅从西向东用1-N来标号。每个住宅有一个人。住宅只会存在于偶数整数点。

    该国国王认为,国民体质下降,必须要多运动,于是下命令所有人都必须出门散步。所有的国民,一秒钟可以走1米。每个国民各自向东或者向西走。这些方向你是知道的。命令发出后所有人同时离开家门开始散步。

    然而该国的国民个都很健谈,如果在散步途中两个人相遇,就会停下来交谈。正在走路的人碰到已经停下来的人(重合)也会停下来交谈。一但停下来,就会聊到天昏地暗,忘记了散步。

    现在命令已经发出了T秒,该国有Q个重要人物,国王希望能够把握他们的位置。你能帮他解答吗?

    输入输出格式

    输入格式:

    第一行是3个整数,N,T,Q

    接下来N行,每行两个整数Ai,Ri。Ai是家的坐标,如果Ri是1,那么会向东走,如果是2,向西。数据保证Ai是升序排序,而且不会有两个人初始位置重合。

    接下来Q行,每行一个整数,表示国王关心的重要人物。

    输出格式:

    Q行,每行一个整数,表示这个人的坐标。

    输入输出样例

    输入样例#1: 复制
    6 6 4
    -10 1
    -6 2
    -4 1
    2 1
    6 2
    18 2
    2
    3
    4
    6
    输出样例#1: 复制
    -8
    2
    4
    12

    说明

    20%数据 N<=100,T<=10000

    另外20%数据 N<=5000

    另外20%数据 从最西边数起连续的若干国民全部往东,剩下的全部往西

    100%数据 Ai为偶数,|Ai|<=10^18,|T|<=10^18,1<=Q<=N<=100000.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。