2023 蓝桥杯热身赛

Problem P18. 周游山区(25 分)

Jerry 成功营救了 Tom ,经过了这一次浩劫,他们决定淡出人们的视线,开始环球旅行,好好放松一下。

他们来到了一个环形山区,在这个山区上有 n 个加油站(多个加油站的位置可能会重叠),每个加油站有若干升汽油(有可能为零),每升汽油可以让汽车行驶一千米。 Tom 和 Jerry 必须从一个加油站出发, 一直 按照顺时针(或 一直 按照逆时针)方向走遍所有车站,并回到起点。

假设一开始,汽车里没有油,他们每到达一个加油站,就将站里所有油都带上(起点亦是如此),行驶过程中不能出现油量为零的情况。请你判断以每个加油站为起点,能否在满足上述条件的情况下环游这个山区一周呢?

输入

第一行包含一个整数 n(3\leq n\leq 10^6) ,表示山区中的加油站个数。

接下来 n 行,每行两个整数 p_i,d_i(0\leq p_i,d_i\leq 2\times 10^9) ,分别表示第 i 个加油站的油量和第 i 个加油站到 顺时针方向 的下一站的距离(第 n 个加油站的下一个站是第 1 个加油站)。

输出

输出共 n 行,如果从第 i 个加油站出发, 一直 按顺时针(或 一直 按照逆时针)方向行驶,环游山区一周,且行驶过程中油量不降到 0 ,则第 i 行输出 YES ,否则输出 NO

样例

标准输入 复制文本
5
3 1
1 2
5 2
0 1
5 4
标准输出 复制文本
YES
NO
YES
NO
YES

提示

行驶过程 定义为从一个加油站出发,直到回到这个加油站之前的瞬间,即若回到起点时,油量恰好为 0 ,也算成功环游一周山区,但在此之前的任何时候,油量都不可为 0

从一个加油站出发,只要按顺时针或逆时针任意一种方向成功环行一周,即可输出 YES

对于 10 分的数据, n\leq 1000

对于 15 分的数据, n \leq 100000

对于 25 分的数据, n \leq 1000000

登录以提交代码。
单点时限 2 秒
内存限制 256 MB
提交 7
通过 0