Dynamic Segment Trees

Правка en3, от noobinho, 2018-07-19 01:53:06

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский noobinho 2018-07-20 19:50:40 1 UP1: Correction of the complexity
en3 Английский noobinho 2018-07-19 01:53:06 346
en2 Английский noobinho 2018-07-19 00:49:08 13
en1 Английский noobinho 2018-07-19 00:19:39 321 Initial revision (published)