페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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번
로그인해야 코드를 작성할 수 있어요.