### magieNoire's blog

By magieNoire, 4 years ago, ,

Hello everyone, I tried recently this problem, but unfortunately I got TLE. I am using an O(nlogn) algorithm as supposed( a segment tree for updating the list and a map to keep track of frequency of each number and it's position ). I think there is some overhead with the update function -- can I rewrite it iteratively ? Any suggestion is welcomed.

Note: if someone can redirect me to a non recursive implementation of segment trees that will be great.

•
• +8
•

 » 4 years ago, # |   +9 I solved it with the same (recursive) approach, but I did not use a map. I compressed the input values by using an auxiliary array (and by sorting it). It passes in 0.171 seconds and 3965 KB.
•  » » 4 years ago, # ^ |   0 Can you please explain more. A tiny example will be perfect :)
•  » » » 4 years ago, # ^ | ← Rev. 5 →   +9 For the sample input: 5 + 8 (i=0) + 6 (i=1) + 8 (i=2) - 8 (i=3) - 8 (i=4) I keep a copy of the input, I sort the "copy" thus getting this: 5 + 6 (i=1) + 8 (i=0) + 8 (i=2) - 8 (i=3) - 8 (i=4) I assign increasing numbers k to "mark" distinct values (in this case there are 2 distinct values): 5 + 6 (i=1) (k=1) + 8 (i=0) (k=2) + 8 (i=2) (k=2) - 8 (i=3) (k=2) - 8 (i=4) (k=2) (while computing this, I store for each i the corresponding k).Then, for each i (from 0 to q - 1), I add/remove the number (which I get from the "original" input) in/from the k-th position.Code here
•  » » » » 4 years ago, # ^ |   0 Thanks dude! Good explanation and good solution too ;)
 » 4 years ago, # |   +5 I've used the segment tree realization, which I know as "Implicit segment tree". The main idea is to build segment tree on whole range of numbers (from 1 to 1000000000 in this problem), but nodes we create only when they are need.My solution passes in 0.187s with VC++ compiler and 0.343s with G++.
•  » » 4 years ago, # ^ |   0 The link that you gave me doesn't work ( empty page ). I am the only one ?You know what I got it accepted with VC++ compiler too. But, I am highly interested in your solution, please fix the problem.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 My solution using an implicit segment tree. There are at most 100000 numbers to store; a root-to-leaf path requires lg(1000000000) ~ 31 nodes in the segment tree. Pre-allocate a pool of nodes of size 100000 * 31, whenever you want to create a new node, fetch it from the pool (faster than malloc-ing at runtime). Update is similar to ordinary segment tree (I use left/right pointers).
 » 3 years ago, # |   0 I've suffered a few days to pass this problem. Even with the right ideia, TLE was the veredict. Then I substitued an iterative approach for the recursive one. Anyway, my iterative update(remove, insert) function is here. Thanks to wil93 for the great solution.
 » 3 years ago, # | ← Rev. 2 →   0 I used the indexing notation of Segment tree (v is the parent of 2*v and 2*v+1) and iterated through the dependent nodes during update; In my solution, On a node I stored gcd due to elements in its left-subtree and gcd due to the elements in its right-subtree. [http://ideone.com/uMRGOV] The space can be reduced also. [http://ideone.com/wqH4Tz]On a side note, I guess, any balanced Tree representation would work. (Fenwick Trees/ Segment Trees/ Online Treaps etc.,). Hope it helps :)
 » 11 months ago, # | ← Rev. 2 →   -8 I am getting WA on the Test-Case #4 . I have stored all the factors of the number with its occurance in an UNORDERED MAP. I have used set to store the minimum element as HCF will be its factor.Here is my code .... It would be a great help if someone could tell me whats wrong. #include using namespace std; #define repl(i,x,n) for(long long i=(long long)(x);i<(long long)(n);i++) #define rep(i,x,n) for(long i=long(x);i m; set s; char c; cin>>n; rep(j,1,n+1) { cin>>c>>x; if(c=='+') { l++; s.insert(x); if(h==-1) { h=x; cout<