让你失望了私人教师 Kuroni

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.

私人老师让我来完成这道私人题目。

para 太牛了，但是为什么这道题的练习题目是 Teoretičar。

有 $n$ 个问题，$m$ 个人，$g_i$ 表示第 $i$ 个人的得分，已知 $q$ 个人的得分：排名为 $p_i$ 的人得分为 $s_i$，$m$ 个人总得分为 $t$。$f_i$ 表示第 $i$ 个问题的答对人数，第 $i$ 个问题至少 $l_i$ 个人答对，至多 $r_i$ 个人答对。现在可以列出已知条件：

因为构成完美匹配，根据霍尔定理：一个二分图 $(V1,V2,E)$ 存在完美匹配当且仅当 $\forall_{S\in V1} |N(S)| \geq |S|$，设 $S$ 中有 $k$ 个人，第 $i$ 个人得分为 $g'_i$，可得：

由于

所以 $g'_i=g_i$ 时限制最强，因此：

令 $G_i$ 表示前 $i$ 个人得分之和的最大值，可以根据上述推得：

同时，由于已知 $q$ 个人的得分，可以加强限制：

如果 $f_i$ 确定，那么可以二分排第一的人数，然后为满足条件：

根据 $G_i$ 贪心的填即可。

现在考虑构造最优的 $f_i$。

由于要最大化排第一的人数，$G_n=t$，所以要最小化一段前缀的 $G_i$。因此为最小化

$f_i$ 需要在满足

的条件下尽可能地小且平均。

实现方面，将题目按照 $l_i$ 从小到大排序，先将通过人数都设为 $l_i$，计算剩余值，每次要补平一段前缀，用剩余值平均分配，同时用一个优先队列维护 $r_i$，每次将预期补平值超过 $r_i$ 的踢出即可，时间复杂度 $O(n \log n)$。