记录编号	423653	评测结果	AAAAAAAAAA
题目名称	[郑州集训 2017]NOI模拟题1.2	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.132 s
提交时间	2017-07-12 11:29:38	内存使用	3.74 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,k,h[N],fa[N],l[N],r[N];
vector<int> son[N];
long long ans,size[N];
void solve(int x){
	l[x]=r[x]=x;
	for (int i=0;i<son[x].size();i++){
		int v=son[x][i];
		solve(v);
		l[x]=min(l[x],l[v]);
		r[x]=max(r[x],r[v]);
	}
	size[x]+=1ll*(r[x]-l[x]+1)*(h[x]-h[fa[x]]);
	if (size[x]>0){
		ll cnt=(size[x]+k-1)/k;
		size[x]-=cnt*k;
		ans+=cnt;
	}
	size[fa[x]]+=size[x];
}
int main()
{
	freopen("er.in","r",stdin);
	freopen("er.out","w",stdout);
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++){
		scanf("%d",&h[i]);
		fa[i]=i-1;
		int last=0;
		while (h[i]<h[fa[i]]) last=fa[i],fa[i]=fa[fa[i]];
		if (last) fa[last]=i;
	}
	for (int i=1;i<=n;i++) son[fa[i]].push_back(i);
	solve(0);
	printf("%lld\n",ans);
	return 0;
}