该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
YH 有 n 把剑,第 i 把剑的攻击力为 ai,防御能力为 bi。
对于一把剑 i,如果存在一个 j(j=i),使得 ai≤aj 且 bi≤bj,那么 YH 就认为这把剑是无用的。反之,他就认为这把剑是有用的。
在本题中,我们保证,不可能找到两把剑 i,j,使得 ai=aj 且 bi=bj。
请你帮助 YH 求出这 n 把剑中,有用的剑的数量。
输入格式
第一行,一个整数 n。
接下来 n 行,每行两个整数 ai,bi,表示第 i 把剑形的攻击力和防御能力。
输出格式
一个整数,表示有用的剑的数量。
样例 #1
样例输入 #1
3
2 3
1 3
5 3
样例输出 #1
1
样例 #2
样例输入 #2
4
5 6
2 5
6 9
1 3
样例输出 #2
1
提示
Subtask |
分值 |
特殊性质 |
1 |
11 |
n≤500 |
2 |
21 |
ai,bi≤500 |
3 |
34 |
ai=i |
4 |
25 |
对于每一个 1≤i<j≤n,有 ai=aj |
5 |
9 |
无 |
对于所有数据,1≤n≤100000,1≤ai,bi≤109。