问题1011--组队(group)

1011: 组队(group)

时间限制: 1 Sec  内存限制: 128 MB
提交: 31  解决: 15
[提交] [状态] [讨论版] [命题人:]

题目描述

Bsny所在的精灵社区有n个居民,每个居民有一定的地位和年龄,ri表示第i个人的地位,ai表示第i个人的年龄。
最近社区里要举行活动,要求几个人组成一个小组,小组中必须要有一个队长,要成为队长有这样的条件:
1.   队长在小组中的地位应该是最高的(可以并列第一),
2.   小组中其他成员的年龄和队长的年龄差距不能超过K
有些人想和自己亲密的人组在同一个小组,同时希望所在的小组人越多越好。比如x和y想在同一个小组,同时希望它们所在的小组人越多越好,当然,它们也必须选一个符合上述要求的队长,那么问你,要同时包含x和y的小组,最多可以组多少人?

输入

首先输入n和K
接下来一行输入n个整数:r1, r2, …, rn
接下来一行输入n个整数:a1, a2, …, an
接下来输入Q表示有Q个询问
接下来Q行每行输入x, y,表示询问:当x和y组在同一个小组,它们小组最多可以有多少人(x和y也有可能被选为队长,只要它们符合条件)

输出

对于每个询问,输出相应的答案
每个答案占一行
当x和y无法在同一组时,输出-1(比如x的年龄是1,y的年龄是100,K=1,无论谁当队长,x和y两者中,总会有人跟队长的年龄差距超过K,那么输出-1)

样例输入 Copy

5 1
1 5 4 1 2
4 4 3 2 2
4
5 3
2 3
2 5
4 1

样例输出 Copy

4
3
-1
4

提示

样例解释:
询问1:当第5个人和第3个人想在一组时,小组成员可以有{1,3,4,5},选择3当队长,而2不可以加入,因为2加入的话,5和2的年龄差距为2,超过K=1了。所以答案为4
询问2:当第2个人和第3个人想在一组时,可以选择{1,2,3}
询问3:当2和5想在一起时,无法满足要求
询问4:当4和1想在一起时,可以选择{1,3,4,5}
数据范围:
20%的数据:
2<=n<=100,  0<=K<=100,  1<=ri, ai <=100,  1<=q<=100
40%的数据:
2<=n<=1000,  0<=K<=1000,  1<=ri, ai <=1000,  1<=q<=1000
60%的数据:
2<=n<=10^4,  0<=K<=10^9,  1<=ri, ai <=10^9,  1<=q<=10^4
100%的数据:
2<=n<=10^5,  0<=K<=10^9,  1<=ri, ai <=10^9,  1<=q<=10^5
1<=x, y<=n, x!=y

来源/分类