IOI '15 - Almaty, Kazakhstan
Teams
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.
Example
Suppose there are N = 4 students and Q = 2 days. The students' constraints on team sizes are given in the table below.
| student | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| A | 1 | 2 | 2 | 2 |
| B | 2 | 3 | 3 | 4 |
On the first day there are M = 2 projects. The required team sizes are K[0] = 1 and K[1] = 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[0] = 1 and K[1] = 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.
Input Format
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[0], K[1], …, 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.
Output Format
For each query, output a separate line containing either 1 if it is possible to form all the required teams, or 0 otherwise.
Sample Input
4 2 4 1 2 2 3 2 3 2 2 1 3 2 1 1
Sample Output
1 0
Subtasks
| subtask | points | N | Q | additional constraints |
|---|---|---|---|---|
| 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 |
All Submissions
Best Solutions
Point Value: 30 (partial)
Time Limit: 5.00s
Memory Limit: 2048M
Added: Sep 05, 2015
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)