/ Vijos / 题库 /

Fish && kitty

Fish && kitty

背景

话说fish和kitty打算去郑州世纪欢乐园玩。因为那里都是些惊险刺激的项目,kitty很害怕,所以她就给fish出了个难题……

描述

世纪欢乐园只有一条单向的路,从入口到出口(别问为什么……出个题不容易),在路边有各种游乐项目。kitty是小MM,她认为骑那么远的车只玩一个项目是不值得的,所以如果只能玩一个项目,她就不去了……因为kitty胆小,所以如果他们玩的相邻两个项目的惊险度差大于h,kitty就会害怕地哭……
世纪欢乐园的各项目的惊险度fish都很清楚。为了和kitty好好玩(当然不能让kitty掉泪),他打算算出有多少种游玩的方案,和他们最多能玩几个项目。但他现在在听音乐,所以任务就是你的了~

例如,有4个项目,惊险度分别是1 3 7 5,而kitty要求相邻两个的惊险度之差不超过2,则他们有1 3;1 3 5;3 5;7 5这4种方案,其中项目最多的方案是3个。

格式

输入格式

输入文件有两行。

第一行有n和h,用空格隔开;2<=n<=100000,0<=h<=1E9
第二行有n个整数,为从入口到出口各个项目的惊险度,空格隔开

输出格式

输出共两行。

第一行输出一个整数,表示方案数。因为方案可能有很多很多,所以你只需输出方案数模198964的余数
第二行输出一个整数,表示最大的方案所包含的项目个数。

如果不存在方案,则两行都输出0。(fish就会和kitty看电影去~)

样例1

样例输入1

4 2
1 3 7 5

样例输出1

4
3

限制

各数据点时限2s

来源

菜鱼闲来无事想kitty……

信息

ID
1183
难度
7
分类
数据结构 | 线段树 点击显示
标签
(无)
递交数
568
已通过
118
通过率
21%
被复制
6
上传者

相关

在下列训练计划中:

noip进阶班2017训练

RP++分类题库