PEG Judge - WC15 #3 - Red Sun Simulator

Woburn Challenge 2015-16 Round 3 - Junior Division

Problem 3: Red Sun Simulator

Being a masterful tactician, Batman wants to take advantage of his opponent's every weakness in battle. Too bad there just aren't many weaknesses of Superman. Though Superman's most famous weakness is Kryptonite, Batman's Kryptonite-laced weapons may still not be enough to help him win. A lesser known weakness of Super is the red sun. The red sun on Krypton is much less radiant than the yellow sun on Earth, which is why native Kryptonians aren't naturally as strong as Superman. It is only because Superman grew up on Earth that his powers are acquainted to and magnified by our powerful yellow sun's radiation.

Without a yellow sun, Superman's powers will be temporarily weakened. Even for Batman, it is quite near impossible to block out yellow sun radiation altogether. However, Batman believes that if he is able to temporarily convert the yellow sun radiation to red sun radiation, then he will be able to weaken Superman to the same effects. With the help of Lucius Fox, WayneTech was able to secretly develop a device to perform this exact conversion. This sophisticated technology, known as the Red Sun Simulator (RSS) will be installed onto the batplane which will idle in the sky during their fight. When the time is right, the device will continuously diffuse electromagnetic waves that will create an interference pattern with the electromagnetic radiation of the sun. The radiation generated by the RSS should be at precise frequencies so that the resulting wave exactly matches the frequency of the red sun of Krypton. Unfortunately for Batman, the frequency of solar radiation is going to be constantly changing due to small factors such as atmospheric conditions and their altitude. Due to these constraints, the ability of the RSS to produce waves at a certain frequency will also be limited.

The masterful tactician he is, Batman has planned out how every moment of the battle is going to go down. In particular, he predicts that there will be N (1 ≤ N ≤ 50000) minutes in the entire battle. During the i-th minute, the frequency of the solar radiation is forecasted to be F_i (1 ≤ F_i ≤ 10⁹) megahertz. In order for Superman to be weakened by red sun radiation during minute i, the frequency produced by the RSS must be a multiple of the solar frequency during that minute. In minute i, the RSS will randomly produce a frequency from a set of M_i (1 ≤ M_i ≤ 5) intervals. The j-th of these intervals will consist of the integers from A_i,j to B_i,j (1 ≤ A_i,j ≤ B_i,j ≤ 10⁹) inclusive, meaning that during minute i, the RSS is capable of emitting radiation at any one frequency from A_i,j megahertz to B_i,j megahertz for any j from 1 to M_i. For each minute i, the M_i intervals will be non-overlapping, meaning that any integer will be part of at most one of the intervals.

Batman is interested in whether he can weaken Superman for a particular number of minutes in total. Thusly, he wants to answer Q (1 ≤ Q ≤ N + 1) questions, where the i-th question is: "is it at all possible to weaken Superman during exactly T_i minutes of the total N minutes of the battle?" (0 ≤ T_i ≤ N). Please write a program to analyze the solar data and answer Batman's queries.

In cases worth 20/30 of the points, F_i ≤ 100 and B_i,j ≤ 100.
In a subset of those cases worth 10/30 of the points, N ≤ 8.

Input Format

The first line will contain two space-separated integers N and Q.
The next N lines will each start with 2 space-separated integers F_i and M_i, followed by M_i space-separated pairs of integers A_i,j and B_i,j (for i = 1..N and j = 1..M_i).
The last Q lines will each contain a single integer T_i (for i = 1..Q).

Output Format

Q lines with one character per line. The i-th of these lines is "Y" if Batman can weaken Superman using simulated red sun radiation during exactly T_i minutes, or "N" otherwise.

Sample Input

4 3
10 3 23 27 1 5 109 110
5 2 7 9 41 42
5 2 7 9 40 42
100 1 100 100
0
2
4

Sample Output

N
Y
N

Explanation

Batman predicts the battle to last a measly 4 minutes. It's impossible for Batman to weaken Superman for 0 minutes, since he'll always be emitting the appropriate frequency to produce red sun radiation the last round (the RSS radiation is fixed at 100 MHz during that minute, which is a multiple of the solar radiation of 100 MHz). It's also impossible for him to weaken Superman in all 4 minutes, since there's no way he can produce red sun radiation in the second minute (the RSS cannot possibly emit a frequency which is a multiple of 5 MHz). However, there are various ways in which Superman can be weakened for exactly 2 minutes, such as if the following frequencies happen to be emitted by the RSS:

1st minute: 110 MHz (producing red sun radiation when interfered with the sun's 10 MHz)
2nd minute: 8 MHz (not producing red sun radiation when interfered with the sun's 5 MHz)
3rd minute: 42 MHz (not producing red sun radiation when interfered with the sun's 5 MHz)
4th minute: 100 MHz (producing red sun radiation when interfered with the sun's 100 MHz)

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 13, 2016
Authors: SourSpinach, Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...