ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
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번
ログインしないとコードを書けません。