#P10728. [NOISG 2023 Qualification] Swords

    ID: 10106 远端评测题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>数学贪心2023排序NOISG(新加坡)

[NOISG 2023 Qualification] Swords

题目描述

YH 有 nn 把剑,第 ii 把剑的攻击力为 aia_i,防御能力为 bib_i

对于一把剑 ii,如果存在一个 j(ji)j(j \not = i),使得 aiaja_i\le a_jbibjb_i\le b_j,那么 YH 就认为这把剑是无用的。反之,他就认为这把剑是有用的。

在本题中,我们保证,不可能找到两把剑 i,ji,j,使得 ai=aja_i=a_jbi=bjb_i=b_j

请你帮助 YH 求出这 nn 把剑中,有用的剑的数量。

输入格式

第一行,一个整数 nn

接下来 nn 行,每行两个整数 ai,bia_i,b_i,表示第 ii 把剑形的攻击力和防御能力。

输出格式

一个整数,表示有用的剑的数量

3
2 3
1 3
5 3

1
4
5 6
2 5
6 9
1 3

1

提示

Subtask\text{Subtask} 分值 特殊性质
11 1111 n500n\le500
22 2121 ai,bi500a_i,b_i\le500
33 3434 ai=ia_i=i
44 2525 对于每一个 1i<jn1\le i<j\le n,有 aiaja_i\not =a_j
55 99

对于所有数据,1n100000,1ai,bi1091\le n\le100000,1\le a_i,b_i\le10^9