L - 長方形 β
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
N 個の長方形があり、長方形 i の幅と高さはそれぞれ A_i, B_i です。
すぬけ君はこれらの長方形の中からいくつかを選んで順番に重ねることで 1 つの模様を作ろうとしています。 このとき、j\ (2 \leq j) 番目に配置する長方形は以下の条件を満たすようにしなければなりません。
- j-1 番目に配置した長方形の内部に完全に含まれる。
- j-1 番目に配置した長方形と辺どうしが接してはならない。
- 各辺は j-1 番目に配置した長方形のいずれかの辺と平行になっていなければならない。
なお、長方形を配置する際は幅と高さを入れ替えても構いません。また、長方形を配置する順番は長方形の番号に関係なく自由に決めることができます。
すぬけ君は最大でいくつの長方形が重なった模様を作ることができるでしょうか?
制約
入力は以下の条件を満たす。
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i,B_i \leq 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 : A_N B_N
出力
すぬけ君が重ねることのできる長方形の個数の最大値を出力せよ。
入力例 1
4 3 4 1 5 5 5 3 1
出力例 1
3
長方形 3、長方形 1、長方形 4 をこの順で図のように配置すると 3 つの長方形を重ねることができます。 長方形の幅と高さを入れ替えても構わない点に注意してください。
入力例 2
3 1000000000 1000000000 1000000000 1000000000 1000000000 1
出力例 2
1
辺どうしが接してはいけない点に注意してください。