问题 6405 --龙哥挑数字

6405: 龙哥挑数字★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 42  解决: 20
[提交][状态][命题人:]

题目描述

给定一个长度为n的数组a和一个长度为m的数组b,以及一个偶数k,龙哥希望能在a和b中各选k/2个元素,现在请帮忙判断一下,龙哥能否使得这些数刚好为1到k范围内的所有整数。
例如:若 a=[2,3,8,5,6,5], b=[1,3,4,10,5], k=6。则可从a中选择 2,3,6,可从b中选择1,4,5,这样1到k所有的数字都选齐了。
若a=[2,3,4,5,6,5], b=[1,3,8,10,3], k=6。则无法选齐1到6所有的整数。

输入

第一行为整数T,表示有T (1≤T≤10000)组测试样例。
每组测试样例第一行为3个整数n,m和k (1≤n,m≤200000, 2≤k≤2*min(n,m), k为偶数) ,分别表示数组a的长度、数组b的长度,以及总共选取元素的数量。
第二行为n个整数a1,a2,…,an(1≤ai≤1e6);第二行为m个整数b1,b2,…,bm(1≤bj≤1e6)。
测试数据保证所有n+m之和不超过400000。

输出

每组测试数据输出一行,若能使选择的数字刚好为1到k范围内的所有整数,则输出YES,否则输出NO。
样例输入
Copy
6
6 5 6
2 3 8 5 6 5
1 3 4 10 5
6 5 6
2 3 4 5 6 5
1 3 8 10 3
3 3 4
1 3 5
2 4 6
2 5 4
1 4
7 3 4 4 2
1 4 2
2
6 4 4 2
1 5 2
3
2 2 1 4 3
样例输出
Copy
YES
NO
YES
YES
NO
NO

提示

在测试样例1中,一种选择方案为从a中选择 2,3,6,从b中选择1,4,5,这样1到k=6所有的数字都选齐了。
在测试样例2中,无法选齐1到6所有的整数。
在测试样例3中,一种选择方案为从a中选择1和3,从b中选择2和4,这样1到k=4所有的数字都选齐了。

来源

[提交][状态]