Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为何超时?请大牛们指点

Posted by gtx at 2008-07-24 21:56:03 on Problem 1195
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define MV 1030
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////2维树状数组/////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
/*
int lowbit(int x)
{
    return x&(x^(x-1));
}
*/
inline int lowbit(int x)
{
    return x&(-x);
}

inline void add_ta2(int (*A)[MV],int n,int x,int y,int v)
{
    int ty;
    while(x<=n)
    {
        ty=y;
        while(ty<=n)
        {
            A[x][ty]+=v;
            ty+=lowbit(ty);
        }
        x+=lowbit(x);
    }
}

inline int sum_ta2(int (*A)[MV],int n,int x,int y)
{
    int sum,ty;
    sum=0;
    while(x>0)
    {
        ty=y;
        while(ty>0)
        {
            sum+=A[x][ty];
            ty-=lowbit(ty);
        }
        x-=lowbit(x);
    }
    return sum;
}
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
int A[MV][MV],n,x,y,x1,y11,v;
int main()
{
	int op;
	while(true)
	{
		scanf("%d",&op);
		switch(op)
		{
		case 0:
			memset(A,0,sizeof(A));
			scanf("%d",&n);
			break;
		case 1:
			scanf("%d %d %d",&x,&y,&v);
			add_ta2(A,n,x,y,v);
			break;
		case 2:
			scanf("%d %d %d %d",&x,&y,&x1,&y11);
			printf("%d\n",sum_ta2(A,n,x1,y11)-sum_ta2(A,n,x-1,y11)-sum_ta2(A,n,x1,y-1)+sum_ta2(A,n,x-1,y-1));
			break;
		case 3:
			return 0;
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator