range tree

Posted by

lxn 9 Jun 2016 16:15

Is there a solution without randge tree structure?

Re: range tree

I use Fenwick Tree get AC,0.452 seconds

Re: range tree

There possible segment tree with uint16_t for indexes greater than 2^15, and uin32_t for less 2^15. (two arrays: uint16_t tree[N+N]; and uint32_t rem[32768] )

But I got WA38 ((

Re: range tree

I Got AC with segment tree!! uraaaaa.

Re: range tree

I can't do that. C/C++.

I am using two cycles.

One to set up Fenwick tree and one to calculate the answer.

Probably you are avoiding the use of the set up cycle somewhat.

I tested my solution on war games 2 and have got 93 ms.

UPD: got 46 ms on version 1

*Edited by author 09.07.2017 22:20*

Re: range tree

Finally, I understood how to get rid of initialization cycle. Still TLE the same test 37.

Re: range tree

Maybe bitwise operations are faster with UNSIGNED integers...

Re: range tree

So, I tried to not calculate cnt=n-i+1 every iteration, made while (1) cycle, not call decrement on Fenwick tree after last soldier.

TLE#37.

Re: range tree

My mistake was

I was using queries for O(log(N) *log(N)) time in Fenwick tree

But for that task, there are suitable queries in just O(log(N))

Re: range tree

You can use segment tree where vertex is segment with length=4.

1 2 3 4 5 6 7 8 9 10 => [1,2,3,4] [5,6,7,8] [9,10,11,12]

Memory is N*sizeof(int)+N*sizeof(bool)

Complexity is N*log(N/4)*4+N*log(N/4)

Re: range tree

decomposition also works here, i've chosen amount of block about 300