#P11280. [COTS 2018] 直方图 Histogram

    ID: 10442 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>CF2200单调栈分治数学数据结构组合数学前缀和

[COTS 2018] 直方图 Histogram

题目描述

给定笛卡尔坐标系中的直方图,宽度为 nn,第 ii 格的高度为 hih_i。也就是说,对于 ∀1≤i≤n\forall 1\le i\le n,第 ii 格所占矩形的顶点坐标分别为 (i−1,0),(i,0),(i−1,hi),(i,hi)(i-1,0),(i,0),(i-1,h_i),(i,h_i)。

给定正整数 pp,求出满足以下条件的矩形的数量:

  • 矩形的四个顶点的坐标均为整数;
  • 矩形有一条边在 xx 轴上;
  • 矩形完全位于直方图内部(可以与边界相切);
  • 矩形的面积至少为 pp。

输入格式

第一行,两个正整数 n,pn,p。

第二行,nn 个正整数 h1,h2,…,hnh_1,h_2,\ldots,h_n。

输出格式

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

输入输出样例 #1

输入 #1

6 9
1 4 4 5 2 3

输出 #1

3

输入输出样例 #2

输入 #2

10 5
3 6 1 3 2 1 5 3 4 2

输出 #2

31

说明/提示

样例解释

样例一解释:

数据范围

对于 100%100\% 的数据,保证:

  • 1≤n≤1051\le n\le 10^5;
  • 1≤p≤10141\le p\le 10^{14};
  • 1≤hi≤1091\le h_i\le 10^{9}。
子任务编号 n≤n\le pp hi≤h_i\le 得分
1 1 3 000 3\, 000 ≤1012\le 10^{12} 109 10^9 10 10
2 2 105 10^5 ≤108\le 10^8 1 0001\, 000 15 15
3 3 105 10^5 =1=1 10910^9
4 4 ≤105\le 10^5 25 25
5 5 ≤1014\le 10^{14} 35 35