my  simple algo don't fit
if compute on each step number of UFO wich
belong to sector - its too long (O(n*n))
What's the correct algo for this task?

You should use cumulative tables...

Octtrees also didn't work! Is there quicker data structure?

Tree Array, like Mobile(IOI2001).

Should call'Binary Indexed Tree'

I use cumulative tables... But I get TLE 5 =(

A[i][j][k][d]=Sum[{i*2^d,j*2^d,k*2^d}:{(i+1)*2^d-1,(j+1)*2^d-1,(k+1)*2^d-1}]

I can add the UFO by log(n) time, but the calculation of the total number of UFOs in a sector are too long... =(

For example, if N=128 and x1=1, y1=1, z1=1, x2=126, y2=126, z2=126 - my algo gives O(n^2) time... =(

My AC program is O((log N)^3) time

Mine's too (base4 due to ML). 1.47 sec

Hm...
My solution uses segment tree in plain array as underlying data structure and it runs in O(n log n) but I've got TLE 6.
Probably it's because I've used java and created a lot of objects while processing.
Will try to tune performance to fit in time bound.

Got the same problem with segment tree and TLE 6, even though I use C++((