P3643 [APIO2016] 划艇

题目描述

在首尔城中,汉江横贯东西。在汉江的北岸,从西向东星星点点地分布着 $N$ 个划艇学校,编号依次为 $1$ 到 $N$。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同,不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典,也可以选择不派出任何划艇参加。如果编号为 $i$ 的学校选择派出划艇参加庆典,那么,派出的划艇数量可以在 $a_i$ 至 $b_i$ 之间任意选择($a_i \leq b_i$)。 值得注意的是,编号为 $i$ 的学校如果选择派出划艇参加庆典,那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。 输入所有学校的 $a_i,b_i$ 的值,求出参加庆典的划艇有多少种可能的情况,必须有至少一艘划艇参加庆典。两种情况不同当且仅当有参加庆典的某种颜色的划艇数量不同。

输入格式

输出格式

说明/提示

【样例解释】 在只有一所学校派出划艇的情况下有 $4$ 种方案,两所学校都派出划艇的情况下有 $3$ 种方案,所以答案为 $7$。 【数据范围】 子任务 $1$($9$ 分):$1 \leq N \leq 500$ 且对于所有的 $1 \leq i \leq N$,保证 $a_i=b_i$。 子任务 $2$($22$ 分):$1 \leq N \leq 500$ 且 $\sum_{i=1}^N (b_i-a_i) \leq 10^6$。 子任务 $3$($27$ 分):$1 \leq N \leq 100$。 子任务 $4$($42$ 分):$1 \leq N \leq 500$。