← 返回题目列表

AtCoder · tessoku_book_cw

B24. 很多盒子

中文机器翻译题面 查看原题

配点: 1000 点

問題文

N 盒子。i 第二个盒子的垂直长度是 X_i 水平长度是 Y_i 。
当同时满足以下两个条件时,盒子 A 可以放置在盒子 B 内。

  • (盒子A的垂直长度) < (盒子B的垂直长度)
  • (盒子A的水平长度) < (盒子B的宽度长度)

最多可以堆叠多少个盒子?
但是,无法旋转盒子并反转垂直和水平长度。

制約

  • 1 \leq N \leq 100000
  • 1 \leq X_i \leq 500000
  • 1 \leq Y_i \leq 500000
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
X_1 Y_1
X_2 Y_2
 :
X_N Y_N

出力

请以整数形式输出答案。


入力例 1

5
30 50
10 30
40 10
50 20
40 60

出力例 1

3

从外部开始, 5, 1, 2”,盒子是 3 可以变得很重。 有一座山,上面有


入力例 2

9
10 90
20 80
30 70
40 60
50 50
60 40
70 30
80 20
90 10

出力例 2

1