题目描述
有 n 个事件,每个事件 (ti,xi) 表示在 ti 时刻,xi 处会降落一颗球球。
小 F t0=0 时刻在 x0=0,现在要去接这些球,要求在 ti 时刻,小 F 或者小 F 的分身在 xi。
若当前时刻小 F 在 x,那么下一时刻他可以移动到 x−1,x 或 x+1。
小 F 可以在任意时刻,在他所处位置放下一个不能移动的分身,可以用分身来接球,但当放下一个分身时,之前存在的分身会在 0.01 时刻后消失。
问小 F 能不能接到所有球。若可以则输出 YES
,否则输出 NO
。
输入格式
第一行一个正整数 n。
接下来的 n 行,每行两个数字,第 i+1 行表示 ti,xi。
输出格式
一行一个字符串,YES
或者 NO
表示答案。
样例数据
样例输入 1
5
2 1
3 2
9 6
10 5
13 0
样例输出 1
YES
样例输入 2
5
30 10
40 -10
51 9
52 8
53 20
样例输出 2
YES
样例输入 3
6
2 1
3 1
5 5
6 1
8 7
8 6
样例输出 3
YES
样例输入 4
10
1 -1
2 -1
3 1
4 2
4 -1
5 3
7 2
8 3
10 -2
11 1
样例输出 4
NO
样例输入 5
3
2 2
5 5
6 1
样例输出 5
YES
数据范围
128MB,1s。
本题有 8 个子任务
Subtask 1(5%),n≤20,特殊性质。
Subtask 2(5%),n≤100,依赖子任务 1,特殊性质。
Subtask 3(10%),n≤5000,依赖子任务 2,特殊性质。
Subtask 4(20%),n≤5000。
Subtask 5(20%),n≤105,依赖子任务 3,特殊性质。
Subtask 6(10%),n≤3×105,依赖子任务 5,特殊性质。
Subtask 7(20%),n≤3×105,依赖子任务 4,6。
Subtask 8(10%),n≤106,依赖子任务 7。
对于全部数据,满足 n≤106,∀i1,ti≥ti−1,∀1≤i≤n,‖。
特殊性质: 满足 x_i 互不相同。