Source Code

Problem: 3250  User: Bzin 
Memory: N/A  Time: N/A 
Language: C++  Result: Wrong Answer 

Source Code 
#include <stdio.h>
#include <string.h>

const int Size=80002;

int N;
int Hight[Size];

void Read()
{
	int i;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
		scanf("%d",&Hight[i]);
}

int Do(int left,int right)
{
	int max;
	int i,j;
	int center;
	int retur;
	if(left==right)
		return 0;
	center=(left+right)/2;
	retur = Do(left,center)+Do(center+1,right);

	j=center+1;
	max=0;
	for(i=center;i>=left;i--)
	{
		if(Hight[i]>max)
		{
			max=Hight[i];
			for(;j<=right;j++)
			{
				if(Hight[j]>=max)
					break;
			}
			retur += j-center-1;
		}
	}
	return retur;
}

int Work()
{
	if(N==1)
		return 0;
	return Do(1,N);
}


int main()
{
//	freopen("in.txt","r",stdin);
	int result;
	Read();
	result=Work();
	printf("%d\n",result);
	return 0;
}


Source Code

Problem: 3250  User: Bzin 
Memory: 516K  Time: 141MS 
Language: C++  Result: Accepted 

Source Code 
#include <stdio.h>
#include <string.h>

const int Size=80002;

int N;
int Hight[Size];

void Read()
{
	int i;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
		scanf("%d",&Hight[i]);
}

unsigned int Do(int left,int right)
{
	int max;
	int i,j;
	int center;
	unsigned int retur;
	if(left==right)
		return 0;
	center=(left+right)/2;
	retur = Do(left,center)+Do(center+1,right);

	j=center+1;
	max=0;
	for(i=center;i>=left;i--)
	{
		if(Hight[i]>max)
		{
			max=Hight[i];
			for(;j<=right;j++)
			{
				if(Hight[j]>=max)
					break;
			}
			retur += j-center-1;
		}
	}
	return retur;
}

unsigned int Work()
{
	if(N==1)
		return 0;
	return Do(1,N);
}


int main()
{
//	freopen("in.txt","r",stdin);
	unsigned int result;
	Read();
	result=Work();
	printf("%u\n",result);
	return 0;
}

• Re:(a1+an)*n/2... ... (0+79999)*80000/2=3199960000, 80000本来就超int类型了,但在unsigned int内 (0) ABD 2008-11-20 18:43:47