QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

# 4906. 球球

统计

题目描述

有 $n$ 个事件,每个事件 $(t_i,x_i)$ 表示在 $t_i$ 时刻,$x_i$ 处会降落一颗球球。

小 F $t_0=0$ 时刻在 $x_0=0$,现在要去接这些球,要求在 $t_i$ 时刻,小 F 或者小 F 的分身在 $x_i$。

若当前时刻小 F 在 $x$,那么下一时刻他可以移动到 $x-1,x$ 或 $x+1$。

小 F 可以在任意时刻,在他所处位置放下一个不能移动的分身,可以用分身来接球,但当放下一个分身时,之前存在的分身会在 $0.01$ 时刻后消失。

问小 F 能不能接到所有球。若可以则输出 YES,否则输出 NO

输入格式

第一行一个正整数 $n$。

接下来的 $n$ 行,每行两个数字,第 $i+1$ 行表示 $t_i,x_i$。

输出格式

一行一个字符串,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\le 20$,特殊性质。

Subtask 2($5\%$),$n\le 100$,依赖子任务 1,特殊性质。

Subtask 3($10\%$),$n\le 5000$,依赖子任务 2,特殊性质。

Subtask 4($20\%$),$n\le 5000$。

Subtask 5($20\%$),$n\le 10^5$,依赖子任务 3,特殊性质。

Subtask 6($10\%$),$n\le 3\times 10^5$,依赖子任务 5,特殊性质。

Subtask 7($20\%$),$n\le 3 \times 10^5$,依赖子任务 4,6。

Subtask 8($10\%$),$n\le 10^6$,依赖子任务 7。

对于全部数据,满足 $n\le 10^6$,$\forall i\>1,t_i\ge t_{i-1}, \forall 1\le i\le n,\|x_i\|\le 10^9, 0\le t_i\le 10^9$。

特殊性质: 满足 $x_i$ 互不相同。