|
|
Show all threads Hide all threads Show all messages Hide all messages | range tree | lxn | 1896. War Games 2.1 | 22 Nov 2021 01:13 | 12 | 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. 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 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. 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)) |
|
|
|