#P1036. B.数字集(tree.cpp)
B.数字集(tree.cpp)
题目描述
一共有 件对数,每对数用 表示 。 你有两类集合,每类都有若干个,你需要将每对数都放入一个集合中。 对于第一类集合,只能放入 严格小于 的数。 对于第二类集合,只能放入 严格小于 的数。
现在有 个第一类集合(如果就可以放入第一类集合 );
以及 个第二类集合(如果就可以放入第二类集合 )
你需要将每个数对都放入一个集合中并且使得大小最大的集合最小。 如果不能放入所有数,输出 。
输入格式
第一行输入三个整数 。 下一行输入 个整数表示 。 下一行输入 个整数表示 。 接下来 行每行两个整数,表示第 对数的 和 。
输出格式
最大集合的大小(数对个数)最小值。
样例 #1
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
3
样例 #2
2 1 3
2 5
2
3 1
5 3
2 2
-1
提示
样例1说明
一种方法:
第一类集合:(5 1) (4 6)放入集合1();(1 8)放入集合2();(8 5)(7 9)(8 7)放入集合3()。
第二类集合:(2 3)放入集合1();(3,3)(7 6)(10 5)放入集合2()。
样例2说明
(5 3)没有集合可放。
数据范围
- 对于 的数据,有 ;
- 对于另外 的数据,有 ;
- 对于另外 的数据,有 ;
- 对于另外 的数据,有 ;
- 对于全部 的数据,有 $1\le n\le 10^6,0\le A,B\le 5\times 10^4,1\le A+B,1\le x_i,y_i,a_i,b_i\le 2\times 10^9$ 。