Обсуждение @ 1470. НЛО @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

TLE KIRILL 27 сен 2006 00:41

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?

Re: TLE Slobodan 27 сен 2006 22:05

You should use cumulative tables...

Re: TLE Vedernikoff Sergey 30 сен 2006 01:50

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

I've used 3d Fenwick's tree to get AC (-) Anton [SUrSU] 30 сен 2006 09:27

Help!!! Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) 29 окт 2007 18:34

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... =(

No subject SuperLight 3 янв 2008 14:16

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

Re: No subject Denis Koshman 6 авг 2008 04:53

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

Fenwick tree - AC 0.5sec on Java. Alex Tolstov 13 мар 2009 02:25

Re: Fenwick tree - AC 0.5sec on Java. Vitalii Arbuzov 23 мар 2011 22:29

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.

Re: Fenwick tree - AC 0.5sec on Java. ONU_Antananarivu 17 июл 2011 11:38

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

Re: TLE CHN_XT 12 окт 2006 13:52

Tree Array, like Mobile(IOI2001).

Re: TLE lijian 9 июл 2007 10:54

Should call'Binary Indexed Tree'

Обсуждение задачи 1470. НЛО