1433. 周游山区(25 分)

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

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

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

输入

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

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

输出

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

样例

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

提示

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

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

对于 1010 分的数据, n1000n\leq 1000

对于 1515 分的数据, n100000n \leq 100000

对于 2525 分的数据, n1000000n \leq 1000000

来源

2021 天梯赛选拔 / 蓝桥杯热身赛

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