QOJ.ac

QOJ

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

#6385. 剑

Statistics

Yan Hao 有 $n$ 把剑,编号从 $1$ 到 $n$。第 $i$ 把剑的攻击力为 $a[i]$,防御力为 $b[i]$。

Yan Hao 认为,如果存在另一把剑 $j$ ($j \neq i$),使得 $a[i] \leq a[j]$ 且 $b[i] \leq b[j]$,那么剑 $i$ 就是“无用”的。也就是说,如果另一把剑 $j$ 的攻击力和防御力都至少不弱于剑 $i$,则剑 $i$ 是无用的。如果一把剑不是无用的,我们称它是“有用”的。

如果两把剑的攻击力和防御力完全相同,则认为它们是等价的。题目保证没有任何两把剑是等价的。

请帮助 Yan Hao 找出他收藏中“有用”剑的数量。

输入格式

程序必须从标准输入读取数据。

第一行包含一个整数 $n$。

接下来的 $n$ 行,每行包含两个空格分隔的整数。第 $i$ 行输入包含 $a[i]$ 和 $b[i]$,分别表示第 $i$ 把剑的攻击力和防御力。

输出格式

程序必须输出到标准输出。

输出应包含一个整数,即“有用”剑的数量。

输出仅包含一个整数。不要打印任何额外文本,例如 “Enter a number” 或 “The answer is”。

数据范围

对于所有测试用例,输入满足以下限制:

  • $1 \leq n \leq 100\,000$
  • $1 \leq a[i], b[i] \leq 10^9$
  • 对于所有 $1 \leq i < j \leq n$,$a[i] \neq a[j]$ 或 $b[i] \neq b[j]$

你的程序将在满足以下限制的输入实例上进行测试:

子任务 分值 附加限制
1 11 $n \leq 500$
2 21 $a[i], b[i] \leq 500$
3 34 $a[i] = i$
4 25 对于每个 $1 \leq i < j \leq n$,$a[i] \neq a[j]$
5 9 无附加限制

样例

样例输入 1

3
2 3
1 3
5 3

样例输出 1

1

说明 1

比较剑 1 和剑 3,我们有 $a[1] = 2 \leq 5 = a[3]$ 且 $b[1] = 3 \leq 3 = b[3]$,所以剑 1 是无用的。

比较剑 2 和剑 1,我们有 $a[2] = 1 \leq 2 = a[1]$ 且 $b[2] = 3 \leq 3 = b[1]$,所以剑 2 是无用的。

剑 3 是唯一有用的剑。

样例输入 2

4
5 6
2 5
6 9
1 3

样例输出 2

1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.