Hi,

I was working on the following problem and I managed to get a

solution, but it's too slow. And I am still in search for a better

algorithm. Please enlighten me.

--------------------------------------------------------------------------------------------

Here's my solution

#include <stdio.h>

int array[200][200][200] = {0};

int main(){

int n;

char c;

if(scanf("%d\n", &n) != 1)

return 1;

while(1){

int sum = 0;

int x = 0, y = 0, z = 0, x2 = 0, y2 = 0, z2 =0, i, j, k,

num=0;

if(scanf("%c", &c) == EOF)

break;

switch(c){

case 'A':

if(scanf("%d %d %d %d\n", &x, &y, &z, &num) !=

4)

return 1;

array[x-1][y-1][z-1] += num;

break;

case 'S':

if(scanf("%d %d %d %d\n", &x, &y, &z, &num) !=

4)

return 1;

array[x-1][y-1][z-1] -= num;

break;

case 'Q':

if(scanf("%d %d %d %d %d %d\n", &x, &y, &z,

&x2, &y2, &z2) != 6)

return 1;

for(i = x; i < x2+1; i++){

for(j = y; j < y2+1; j++){

for(k = z; k < z2+1; k++){

sum+=array[i-1][j-1][k-1];

}

}

}

printf("%d\n", sum);

break;

default:

goto end;

break;

}

}

end:

return 0;

}

--------------------------------------------------------------------------------------------

This is the question

Prince Ray wants to marry his girl friend, beautiful Princess Amy. Amy

loves Ray, and is very willing to take him. However, Amy's father,

King StreamSpeed, insists that his son in law should be talented

enough, so that he could let him be the King of this country after

King StreamSpeed retired. So he gives Ray a Test.

Ray is given a large brick of size n*n*n, which contains n*n*n grids

of size 1. Every grid can be represent as a triple(x, y, z) (1<=x, y,

z<=n). There are numbers in every grid. All the numbers are initially

set to zero.

King StreamSpeed will do three operations to the brick.

1. Add a number to a given grid's number

2. Subtract a number from a given grid's number

3. Query the sum of total number from(x1,y1,z1) to (x2,y2,z2)

(x1 <= x2, y1 <= y2, z1 <= z2)

As Ray 's best friend and most excellent coder, you are required to

write a program to answer all the queries to help Ray marry with her

valentine.

ÊäÈë

The first line of the input contains an integer n(1<=n<=100), the size

of the brick. Then follow several lines in the following format:

A x y z num : Add num to (x, y, z)

S x y z num: Subtract num from (x, y, z)

Q x1 y1 z1 x2 y2 z2 : Query the sum of numbers from (x1, y1 , z1) to

(x2 , y2 , z2)

The number of all the queries will be no more than 1000000.Input file

is ended by a zero and should not be processed.

Êä³ö

For every query in the input file, your program should output the

corresponding result -- the sum of numbers in the range (x1, y1, z1)

~(x2, y2, z2). The result does not exceed 10^9.

ÑùÀýÊäÈë

10

A 1 1 4 5

A 2 5 4 5

Q 1 1 1 10 10 10

S 3 4 5 34

Q 1 1 1 10 10 10

0

ÑùÀýÊä³ö

10

-24

ÌáÊ¾

Huge input file, scanf is recommended.