1955. 三体·Round - 阶梯计划

时间限制 1000 ms   内存限制 256 MB

“只送大脑。”

核弹已经在预计轨道安放完毕。 载有云天明大脑的储藏仓已经预备。 只等待爆炸的开始。

本题从简考虑,假设储藏仓的预计轨道为一条一维数轴上的、向右无限延伸的射线 而且,只考虑射线上坐标为整数的点 射线的端点坐标为0,储藏仓开始就在坐标为0的位置。 储藏仓有一个能量值,初始为0,能量值可以累计。

当储藏仓能量值为p的时候,储藏仓每向右前进一个单位长度,能量值会减小1点,当能量值为0的时候,储藏仓不能再向右移动。

有n个核弹固定在某些坐标位置,第i个核弹在坐标为xi的位置,有vi的推动力 我们认为,如果储藏仓经过xi时,引爆第i个核弹,那么核弹会给储藏仓增加vi点能量值。

所以,如果在恰当的时候引爆恰当的核弹,储藏仓可以逐渐向右移动。 但是,有些位置是储藏仓无论如何无法移动到的。

现在,有Q个询问,每个询问是一个正整数k,表示询问储藏仓能否移动到坐标为k的位置

保证第0号位置有一个核弹。保证同一个位置没有两个核弹。

输入数据

第一行一个正整数n,表示有n个核弹$(1<=n<=100000)$
接下来n行,第i$(1<=i<=n)$行有两个正整数xi,vi,表示第i个核弹的坐标和推动力。$(0 \leq x_i \leq 10^9,1 \leq v_i \leq 1000)$
保证$x_1=0$且对于任意的

$1<=i<=n-1$, $x_{i+1} \geq x_i$
即,核弹的位置是单调递增排列的。

接下来一个数Q,表示询问的个数$(1<=Q<=100000)$
接下来Q行,每行一个数k$(0<=k<=10^9)$,表示这次询问坐标为k的位置储藏仓是否能到达。

输出数据

输出一共Q行。
对于每一个询问,如果储藏仓能到达,输出Yes,否则输出No(注意大小写)

样例输入

复制
4
0 3
2 4
7 1
9 1000
4
0
9
8
7 \n
 · \n
 · \n
 · \n
 ·    \n
 \n
 \n
 \n
 \n
 \n

样例输出

复制
Yes
No
Yes
Yes   \n
  \n
   \n
   \n

样例说明

对于第四个询问,即k=7时,
储藏仓从0开始,引爆第一颗核弹,此时能量值为3
储藏仓可以到达2位置,此时能量为1,引爆第二颗核弹,能量值变为5
储藏仓可以恰好到达7位置,此时能量为0。
所以对于第四个询问,输出Yes

提交

请先 登录

© 2024 FAQs Contact About