页面无法加载？点击这里可能会修复。
Placeholder

#5926

검 1s 1024MB

问题

정올이는 1부터 n까지 번호가 매겨진 n개의 검을 가지고 있다. 검 i의 공격력은 a[i]이고 방어력은 b[i]이다.

정올이는 다른 검 j(j \neq i)의 공격력과 방어력이 아래와 같으면 검 i는 쓸모가 없다고 생각한다. 쓸모가 없지 않다면 쓸모가 있다고 판단한다.

  • a[i] ≤ a[j] 그리고 b[i] ≤ b[j].

공격력과 방어력이 동일하면 동등한 것으로 간주되는데, 어떤 쌍의 검도 동일하지 않다는 것이 보장된다.

정올이를 위해 쓸모 있는 검의 수를 찾는 프로그램을 작성하시오.


输入

첫 줄에 정수 n이 주어진다. (1 ≤ n ≤ 100,000)

두 번째 줄부터 i번째 줄에 검 i의 공격력과 방어력을 의미하는 a[i], b[i]가 주어진다. (1 ≤ a[i], b[i] ≤ 10^9)

모든 1 ≤ i < j ≤ n에 대하여 a[i] \ne a[j] 이거나 b[i] \ne b[j]이다. 


输出

쓸모 있는 검의 수를 출력한다.


子任务

编号 分数 条件
#111分

n ≤ 500

#221分

a[i],b[i] ≤ 500

#334分

a[i]=i

#425分

a[i] \neq a[j] (1 ≤ i \le j \le n)

#59分

추가 제한 없음


示例 #1

3
2 3
1 3
5 3
1

示例 #2

4
5 6
2 5
6 9
1 3
1

来源

NOI 2023 Qualification 2번
需要登录才能编写代码。