ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1896. War Games 2.1

range tree
Posted by lxn 9 Jun 2016 16:15
Is there a solution without randge tree structure?
Re: range tree
Posted by Shen Yang 23 Aug 2016 17:26
I use Fenwick Tree get AC,0.452 seconds
Re: range tree
Posted by xurshid_n 17 Jan 2017 16:33
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
Posted by xurshid_n 17 Jan 2017 20:57
I Got AC with segment tree!! uraaaaa.
Re: range tree
Posted by Mahilewets 9 Jul 2017 21:42
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
Posted by Mahilewets 9 Jul 2017 22:39
Finally,  I understood how to get rid of initialization cycle. Still TLE the same test 37.
Re: range tree
Posted by Mahilewets 9 Jul 2017 22:47
http://ideone.com/cUMY7U
I have no idea what can be optimized.
Re: range tree
Posted by Mahilewets 9 Jul 2017 22:57
Maybe bitwise operations are faster with UNSIGNED integers...
Re: range tree
Posted by Mahilewets 10 Jul 2017 13:24
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
Posted by Mahilewets 6 Aug 2017 15:09
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
Posted by Felix_Mate 27 Feb 2018 21:41
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
Posted by 🙂 Nayami_[PermSU] 22 Nov 2021 01:13
decomposition also works here, i've chosen amount of block about 300