A13168. Kuroni the Private Tutor
编程题
普及/提高-
知识点
题目描述
As a professional private tutor, Kuroni has to gather statistics of an exam. Kuroni has appointed you to complete this important task. You must not disappoint him.
The exam consists of $n$ questions, and $m$ students have taken the exam. Each question was worth $1$ point. Question $i$ was solved by at least $l_i$ and at most $r_i$ students. Additionally, you know that the total score of all students is $t$ .
Furthermore, you took a glance at the final ranklist of the quiz. The students were ranked from $1$ to $m$ , where rank $1$ has the highest score and rank $m$ has the lowest score. Ties were broken arbitrarily.
You know that the student at rank $p_i$ had a score of $s_i$ for $1 \le i \le q$ .
You wonder if there could have been a huge tie for first place. Help Kuroni determine the maximum number of students who could have gotten as many points as the student with rank $1$ , and the maximum possible score for rank $1$ achieving this maximum number of students.
The exam consists of $n$ questions, and $m$ students have taken the exam. Each question was worth $1$ point. Question $i$ was solved by at least $l_i$ and at most $r_i$ students. Additionally, you know that the total score of all students is $t$ .
Furthermore, you took a glance at the final ranklist of the quiz. The students were ranked from $1$ to $m$ , where rank $1$ has the highest score and rank $m$ has the lowest score. Ties were broken arbitrarily.
You know that the student at rank $p_i$ had a score of $s_i$ for $1 \le i \le q$ .
You wonder if there could have been a huge tie for first place. Help Kuroni determine the maximum number of students who could have gotten as many points as the student with rank $1$ , and the maximum possible score for rank $1$ achieving this maximum number of students.
输入格式
The first line of input contains two integers ( $1 \le n, m \le 10^{5}$ ), denoting the number of questions of the exam and the number of students respectively.
The next $n$ lines contain two integers each, with the $i$ -th line containing $l_{i}$ and $r_{i}$ ( $0 \le l_{i} \le r_{i} \le m$ ).
The next line contains a single integer $q$ ( $0 \le q \le m$ ).
The next $q$ lines contain two integers each, denoting $p_{i}$ and $s_{i}$ ( $1 \le p_{i} \le m$ , $0 \le s_{i} \le n$ ). It is guaranteed that all $p_{i}$ are distinct and if $p_{i} \le p_{j}$ , then $s_{i} \ge s_{j}$ .
The last line contains a single integer $t$ ( $0 \le t \le nm$ ), denoting the total score of all students.
The next $n$ lines contain two integers each, with the $i$ -th line containing $l_{i}$ and $r_{i}$ ( $0 \le l_{i} \le r_{i} \le m$ ).
The next line contains a single integer $q$ ( $0 \le q \le m$ ).
The next $q$ lines contain two integers each, denoting $p_{i}$ and $s_{i}$ ( $1 \le p_{i} \le m$ , $0 \le s_{i} \le n$ ). It is guaranteed that all $p_{i}$ are distinct and if $p_{i} \le p_{j}$ , then $s_{i} \ge s_{j}$ .
The last line contains a single integer $t$ ( $0 \le t \le nm$ ), denoting the total score of all students.
输出格式
Output two integers: the maximum number of students who could have gotten as many points as the student with rank $1$ , and the maximum possible score for rank $1$ achieving this maximum number of students. If there is no valid arrangement that fits the given data, output $-1$ $-1$ .
输入输出样例
输入 #1
5 4 2 4 2 3 1 1 0 1 0 0 1 4 1 7
输出 #1
3 2
输入 #2
5 6 0 6 0 6 2 5 6 6 4 6 1 3 3 30
输出 #2
-1 -1
说明/提示
For the first sample, here is one possible arrangement that fits the data:
Students $1$ and $2$ both solved problems $1$ and $2$ .
Student $3$ solved problems $2$ and $3$ .
Student $4$ solved problem $4$ .
The total score of all students is $T = 7$ . Note that the scores of the students are $2$ , $2$ , $2$ and $1$ respectively, which satisfies the condition that the student at rank $4$ gets exactly $1$ point. Finally, $3$ students tied for first with a maximum score of $2$ , and it can be proven that we cannot do better with any other arrangement.
Students $1$ and $2$ both solved problems $1$ and $2$ .
Student $3$ solved problems $2$ and $3$ .
Student $4$ solved problem $4$ .
The total score of all students is $T = 7$ . Note that the scores of the students are $2$ , $2$ , $2$ and $1$ respectively, which satisfies the condition that the student at rank $4$ gets exactly $1$ point. Finally, $3$ students tied for first with a maximum score of $2$ , and it can be proven that we cannot do better with any other arrangement.