2319804_ac_92ms_672k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

long N;
long h[80001];
long r[80001];

int main()
{
	long i, j;
	__int64 t, ans = 0;

	scanf("%ld",&N);
	for(i = 0; i < N; i++)
		scanf("%ld",&h[i]);
	t = 0;r[N-1] = N;
	for(i = N-2; i >= 0; i--)
	{
		if(h[i]<=h[i+1])
			r[i] = i+1;
		else
		{
			j = i+1;
			do
			{
				j = r[j];
			}while(j<N&&h[i]>h[j]);
			r[i] = j;ans += j-i-1;
		}
	}
	printf("%I64d\n",ans);
	return 1;
}