luogu#P10837. 『FLA - I』云音泛

    ID: 14772 远端评测题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 4 上传者: 标签>模拟离散化洛谷原创O2优化排序前缀和队列差分洛谷月赛

『FLA - I』云音泛

题目背景

English statement. You must submit your code at the Chinese version of the statement.

“……这些年来,过得可好?”

“……无所谓好或不好,人生一场空虚大梦,韶华白首,不过转瞬。惟有天道恒在,往复循环,不曾更改...”

题目描述

在梦中,秋种下了 nn 朵凋零玫瑰。他记得,第 ii 朵玫瑰是在时刻 tit_i 种植的。

凋零玫瑰在被种下的那个时刻就立即开放,但每一株玫瑰只会开放 mm 个时刻(在时刻 TT 种植的玫瑰会且仅会在从时刻 TT 到时刻 T+m1T+m-1mm 个时刻开放),在 mm 个时刻后便化作再也无法挽留的灰尘,飘散在凛冽的寒风中。

他问你,假如他可以改变不超过一朵玫瑰的种植时间(选定一个 tit_i 并将其修改为任意正整数),那么最多有多少个时刻有且仅有一株凋零玫瑰开放?

输入格式

第一行输入两个正整数 n,mn,m

第二行输入 nn 个正整数,第 ii 个正整数为 tit_i

输出格式

输出一行一个正整数表示答案。

5 4
11 9 1 3 12

14

13 7
6 42 58 41 20 60 2 61 45 28 45 28 12

38

提示

「样例解释 #1」

如图,使用金色标记有且仅有一株凋零玫瑰开放的时刻,使用黑色和红色标记每朵凋零玫瑰开放的时刻。

example1

将使用红色标记的玫瑰的种植时刻改为 1717(将 t1t_1 的值修改为 1717,如下图)后有 1414 个时刻有且仅有一株凋零玫瑰开放。可以证明不存在能够使有且仅有一株凋零玫瑰开放的时刻数量大于 1414 的修改方案。

example2

「数据范围」

测试点编号 nn \leq mm \leq tit_i \leq
161 \sim 6 50005000
7127 \sim 12 2×1052 \times 10^5 2×1052 \times 10^5
131413 \sim 14 11 10910^9
152015 \sim 20 2×1052 \times10^5 10910^9

对于所有测试数据,1n2×1051 \leq n \leq 2 \times 10^51m,ti1091 \leq m,t_i \leq 10^9