Scouts on Ranging
All submissions for this problem are available.
During the summer, the boy-scouts group decides to go out for a ranging. The teacher-in-charge Mr. Anderson is faced with the tough job of forming groups for this ranging. Every student in the boy-scouts group has a rank. Now Mr. Anderson has to ensure that every group has a group leader whose rank is greater than or equal to the other group members rank, and his age should not differ from the other members in the group by more than K years.
Now many students are friends and they want their group to be as large as possible.
So they approach Mr. Anderson in pairs to ask the largest group size in which that pair can be accommodated.
Since the scouts are large in number, Mr. Anderson is finding it difficult to answer the students and hence comes to you to solve his problem.
First line contains two integers N (1 ≤ N ≤ 100000) and K(1 ≤ K ≤ 107), number of scouts and the age difference limit in a group. Each scout has a unique serial number from 1 to N.
Next line contains N space separated integers r1,r2,...,rN (1 ≤ ri ≤ 109), representing the ranks of scouts in order of their serial number. Ranks may be same for two scout.
Then next line again contains N integers a1,a2,...,aN (1 ≤ ai ≤ 109), representing the age of scouts in order of their serial number.
Next line contain number of queries, q (1 ≤ q ≤ 105). Then q lines follow.
ith line contains two integers each Xi and Yi separated by a space, the serial number of the scouts who need be accommodated to largest group.
Output q lines, each containing an integer, maximum group size in which the two scouts queried Xi and Yi can be accommodated. The scouts may or may not be the leader of the group.
Input: 6 1 2 5 3 4 3 4 2 4 3 2 1 3 3 2 6 3 6 2 4 Output: 3 5 -1 Explanation: For the first query, Serial number are 2 and 6, the largest group size is 3 (serial 2,3,6), group leader is 2.
For the second query, Serial number are 3 and 6, the largest group size is 5 (serial 1,3,4,5,6),
group leader is 4.
In third query, scout 2 has maximum rank, so he is leader, but his age difference with scout 4 is 2,
violating the age restriction. Hence no group can be formed.
|Time Limit:||0.247525 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.