降温(hard)
题号:NC282065
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

(本题和easy版题意相同,仅数据范围不同。判定未知的气温也有不同,请勿直接复制本题代码交到easy版!)

天气开始降温了。

如果某一天的温度比前一天降低的值不小于x,小红就会认为这是一场“寒潮”。
现在给定了每天的气温,但有一些日子的气温是未知的。小红想知道,发生寒潮的次数的最大值和最小值是多少?
注:我们认为,每天气温的值域一定在[-5*10^8,5*10^8]

输入描述:

第一行输入两个正整数n,x,代表总天数、以及寒潮的判定标准。
第二行输入n个整数a_i,代表每天的气温。特殊的,如果a_i为-999999999,代表这一天的气温是未知的。
1\leq n,x \leq 10^5
-5*10^8 \leq a_i \leq 5*10^8或者a_i=-999999999

输出描述:

两个整数,代表寒潮数量的最大值和最小值。

示例1

输入

复制
3 10
50 -999999999 -50

输出

复制
2 1

说明

第二天的气温未知,若这一天的气温在[41,50]或者[-50,-41],则共有1天寒潮;否则是两天寒潮。
示例2

输入

复制
4 100
-999999999 -999999999 -999999999 -999999999

输出

复制
3 0

说明