IOI '15 - Almaty, Kazakhstan
There is a class of N students, numbered 0 through N − 1. Every day the teacher of the class has some projects for the students. Each project has to be completed by a team of students within the same day. The projects may have various difficulty. For each project, the teacher knows the exact size of a team that should work on it.
Different students may prefer different team sizes. More precisely, student i can only be assigned to a team of size between A[i] and B[i] inclusive. On each day, a student may be assigned to at most one team. Some students might not be assigned to any teams. Each team will work on a single project.
The teacher has already chosen the projects for each of the next Q days. For each of these days, determine whether it is possible to assign students to teams so that there is one team working on each project.
Suppose there are N = 4 students and Q = 2 days. The students' constraints on team sizes are given in the table below.
On the first day there are M = 2 projects. The required team sizes are K = 1 and K = 3. These two teams can be formed by assigning student 0 to a team of size 1 and the remaining three students to a team of size 3.
On the second day there are M = 2 projects again, but this time the required team sizes are K = 1 and K = 1. In this case it is not possible to form the teams, as there is only one student who can be in a team of size 1.
Your are given the description of all students: N, A, and B, as well as a sequence of Q queries — one about each day. Each question consists of the number M of projects on that day and a sequence K of length M containing the required team sizes. The sum of M across all queries will be equal to S(not given in the input). For each question, your program must return whether it is possible to form all the teams.
Line 1 of input will contain a single integer N, representing the number of students.
Lines 2, …, N + 1 will each contain a pair of space-separated integers A[i] and B[i], representing the length N arrays A and B, where A[i] is the minimum team size for student i and B[i] is the maximum team size for student i.
Line N + 2 will contain a single integer Q, representing the number of queries to follow.
Lines N + 3, …, N + Q + 2 will each consists of a query in the format M, K, K, …, K[M − 1]. M represents the number of projects for this day and K is an array of length M containing the required team size for each of these projects.
For each query, output a separate line containing either 1 if it is possible to form all the required teams, or 0 otherwise.
4 2 4 1 2 2 3 2 3 2 2 1 3 2 1 1
|1||21%||1 ≤ N ≤ 100||1 ≤ Q ≤ 100||none|
|2||13%||1 ≤ N ≤ 100,000||Q = 1||none|
|3||43%||1 ≤ N ≤ 100,000||1 ≤ Q ≤ 100,000||S ≤ 100,000|
|4||23%||1 ≤ N ≤ 500,000||1 ≤ Q ≤ 200,000||S ≤ 200,000|
Point Value: 30 (partial)
Time Limit: 5.00s
Memory Limit: 2048M
Added: Sep 05, 2015
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3