传统题 1000ms 256MiB

huhe的导弹系统

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

huhe研发出一种新型导弹拦截系统,你说他牛不!!!!

该系统每次只能拦截一枚导弹。每枚导弹有两个唯一且不可分割的关键参数:高度(h)和速度(v),保证没有两枚导弹的参数完全相同。

拦截系统必须满足以下拦截规则:

若拦截导弹B,则必须满足其高度不超过前一枚拦截导弹A的高度(h_B ≤ h_A)

同时其速度不超过于前一枚拦截导弹A的速度(v_B ≤ v_A)

给定n枚导弹的参数(所有导弹的(h,v)对保证唯一),请计算该拦截系统最多能拦截多少枚导弹。

Format

Input

第一行包含一个整数 n(1 ≤ n ≤ 10000),表示导弹数量 接下来n行,每行包含两个整数h和v(0 ≤ h,v ≤ 10^9),表示导弹的高度和速度

Output

输出一个整数,表示最多能拦截的导弹数量

Samples

8
389 207
155 300
299 200
170 155
158 65
300 299
200 100
100 150
4

Limitation

输入保证所有导弹的(h,v)对唯一

必须严格满足h_B ≤ h_A且v_B ≤ v_A才能拦截

最终答案是最长的满足条件的拦截序列长度

Example explanation

一种最优拦截顺序:

拦截(300,299)

拦截(299,200)(300≥299且299≥200)

拦截(200,100)(299≥200且200≥100)

拦截(158,65)(200≥158且100≥65)

红盾周日下午班

未参加
状态
已结束
规则
OI
题目
12
开始于
2025-4-5 18:45
结束于
2025-4-5 21:45
持续时间
3 小时
主持人
参赛人数
8