Is there a solution without randge tree structure?

I use Fenwick Tree get AC,0.452 seconds

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

I Got AC with segment tree!! uraaaaa.

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

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

http://ideone.com/cUMY7U
I have no idea what can be optimized.

Maybe bitwise operations are faster with UNSIGNED integers...

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.

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))

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)

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