体育课上,n个小朋友排成一行(从1到n编号),老师想把他们分成若干组,每一组都包含编号连续的一段小朋友,每个小朋友属于且仅属于一个组。
第i个小朋友希望它所在的组的人数不多于d[i],不少于c[i],否则他就会不满意。
在所有小朋友都满意的前提下,求可以分成的组的数目的最大值,以及有多少种分组方案能达到最大值。
F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register | 捐赠本站 |
---|
体育课上,n个小朋友排成一行(从1到n编号),老师想把他们分成若干组,每一组都包含编号连续的一段小朋友,每个小朋友属于且仅属于一个组。
第i个小朋友希望它所在的组的人数不多于d[i],不少于c[i],否则他就会不满意。
在所有小朋友都满意的前提下,求可以分成的组的数目的最大值,以及有多少种分组方案能达到最大值。
第一行一个整数n(1<=n<=1000000),表示小朋友的数目。
接下来n行,每行两个整数c[i],d[i](1<=c[i]<=d[i]<=n),表示i所在组的人数的最小值和最大值。
如果不存在这样的方案,仅输出一行NIE。
否则输出一行包含两个整数,组的数目的最大值、方案数量。(方案数量对1000000007取模)