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 。
来源
2021 天梯赛选拔 / 蓝桥杯热身赛