z-green

can somebody help me with this task?

what am i doing wrong?

http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100015736

here is the idea. i convert each single coordinate x,y,z into a unique integer(i think so), and i use BIT to count how many of them are in given borders.

could someone look at the code and help me?

You can't do that because not all points with index lower than some index x correspond to points contained in parallepiped (0,0,0) - point_of_x.

Use 3D BIT instead, where you have 3 dimensions one nested inside another. Like this:
int BIT[ MAX ][ MAX ][ MAX ];

that was my 1. idea, but i thought maybe this could work :)

I'll give you a snippet from my code:

int query( int a, int b, int c )
{
int suma = 0;

for( int i = a+1; i > 0; i -= i&-i )
for( int j = b+1; j > 0; j -= j&-j )
for( int k = c+1; k > 0; k -= k&-k )
suma += F[i][j][k];

return suma;
}

This is how querying works. Updating is done in a similiar way.

ah, it should be suma += F[ i ][ j ][ k ]
:)

And of course your idea doesn't work. Obvious, isn't it? :)

i meant that 3D BIT was my 1. idea, but out of simplicity i thought that 1D BIT with converting could work

it does, look at my solution :)

i have submited this task with 3D (test worked) and again i got all WA.

what did i do wrong?
http://www.z-trening.com/new/www/html/submit.php?submit=7100015772&subm_code=1

U cant just make a difference of two, kvadra ne znam na engleskom :) So u have to include some, minus some others. Your BIT functions are ok

"kvadar" is supposed to be "squared solid"... :S I haven't heard of other expression...

yeah, I guess that's it :)

This formula is wrong: (sum(d,e,f))-(sum(a-1,b-1,c-1))

I recommend getting a rubik cube in your hands, it will be easier to find the formula :)

I'm having some problems with this task.
The idea was to save the coordinates of all the green blocks to an array(and make sure that there are no duplicate blocks in the array),and then simply search the array for the coordinates that match the case.
But for some reason i get all WAs.

Anyways,here's the source code and i'd appreciate if anyone would take a look at it and point out what's wrong.

http://www.z-trening.com/new/www/html/submit.php?submit=7100045471&subm_code=1

Hint:

http://slike.hr/slika.php?z=2dbit0.jpg

This is for 2D bit. You want to find the sum of values between A and B.

Querying A would give you the sum from that yellow rectangle, querying B would give you the sum from all 4 rectangles: yellow one, dark green one and both light green added together. Both of course, you don't need these light green rectangles.

Figure it out how to adapt this to 3D.

But why would i want to "query" or "sum" the rectangles?
Can't i just check if point's coordinates fall inside those borders?(i.e. for a point C Xc >= Xa , Xc<=Xb and Yc>=Yb,Yc<=Ya )

Too slow. Try to calculate its complexity.

it's complexity is O( M^2 )..M = 20 000, it's too much

I don't mean checking all the blocks in the cube,only the ones that have previously been painted green.
Maybe i haven't explained the principle of the algorithm.When a green block is set via ADD command,i save the coordinates in an array(i.e. G[20000][3] where G[i][0] is x coordinate of an i-th green block,G[i][1] is y and G[i][2] is z).When a query comes up,i read in the coordinates of the points and search the array G for all points whose coordinates are x1<=x<x2, y1<=z<=y2 and z1<=z<=z2 .
It seems logical and worked for the sample input.

And the problem isn't in time,i'm always getting wrong result.

if ((g[j][0]>=x1 && g[j][0]<=x2) && (g[j][1]>=y1 && g[j][1]<=y2) && (g[j][2]>=z1 && g[j][1]<=z2) ) count++;

check this line, you have typo when you are checking for z coordinate.

anyway, if you got accepted, then it only tells that test data is weak..because algorithm with complexity O( M lg^3 N ) is expected for this problem.

Yeah,tnx,i got accepted