### noobinho's blog

By noobinho, history, 3 months ago, ,

I'm trying to solve the problem: http://acm.timus.ru/problem.aspx?space=1&num=1439. It consists basically in m (1 <= m <= 10^5) queries in an ordered set which can be of two types: 1) eliminate an element of the ordered set (the number of elements eliminated is at most 10^4); 2) find the kth element of the ordered set. The ordered set can have at most n elements (1 <= n <= 10^9).The elements are {1,2,...,n} at the beginning. I tryed to code a dynamic segment tree to solve in O(m*logn) of time, as follows:https://ideone.com/e.js/jLFIMv. However, it gave MLE. So, I want to know what I can do to improve the memory used. Thanks in advance

 » 3 months ago, # |   0 Why do you indent your code so weirdly?
•  » » 3 months ago, # ^ |   0 Sorry for the bad habits :) Is it better? https://ideone.com/e.js/jLFIMv
 » 3 months ago, # |   0 Auto comment: topic has been updated by noobinho (previous revision, new revision, compare).
 » 3 months ago, # |   0 Auto comment: topic has been updated by noobinho (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   0 At the current time your node is 32 bytes size. You can use indexes in array / vector against pointers because one pointer is 8 bytes, but one index is 4 bytes (32-8=24, 66% memory). You exactly need to keep integers l and r in node? Maybe you can put l and r as parameters in functions in "set" and "get" queries?
•  » » 3 months ago, # ^ |   0 With the contraints that were given (1 <= n <= 10^9) I think it's infeasible to use indexes in array. I think the only way is doing the segment tree with pointers and dynamically. It would be possible to use a segment tree in an array if it was possible to do a compression in the elements of the ordered sets (an offline solution), but I can't realize how to do that.
•  » » » 3 months ago, # ^ | ← Rev. 4 →   0 I mean that we have a vector, that contains nodes. Root has index 0. When we add child, we do push back in end and save value (int)tree.size()-1 as index of child.UPD: Accepted with 52 MB memoryUPD 2: Accepted with 26 MB memoryAs you can see, optimizations of using memory, which I said, works
•  » » » » 3 months ago, # ^ |   0 Wow, thank you! It was really helpful
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 It was helpful for me too, because I did not know about Dynamic Segment Tree before, can you provide a list on problems which can be easy solved with this structure, maybe on coseforces?And your solutions works in O(mlog(n)) time
•  » » » » » » 3 months ago, # ^ |   0 I didn't know this structure before this problem. In fact, I'm doing a list that my teacher gave me and there is only this problem about dynamic segment trees there, but there is a post from three years ago in codeforces with another problems: https://codeforces.com/blog/entry/19080Yes, I realized that my solution works in O(m*logn). I think it would work in O(m*logn²) if I used updateSegTree(query(num,Root,1,n),-1,Root); but as I did q = query(num,Root,1,n); and after updateSegTree(q,-1,Root,1,n); it works in O(m*logn). Is it correct?
•  » » » » » » » 3 months ago, # ^ |   0 On each set or get query you add new log(n) vertices, so it is O(m * log(n)), thanks for link
 » 3 months ago, # | ← Rev. 2 →   0 Is there an offline solution to this problem? In the comments (at the forum of the online judge) a person argued that he did a solution in O(m*logm). If it isn't an offline solution, how to do that?
•  » » 3 months ago, # ^ |   0 Up!I'm very curious to know if there exists an offline solution to this problem
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 Deleted
 » 3 months ago, # |   0 Auto comment: topic has been updated by noobinho (previous revision, new revision, compare).