Is there a way to get 100/100 with Segment Trees for IOI 2013 — Game ?

Правка en1, от damien_g, 2015-07-03 11:14:49

Hello Codeforces!

I implemented a solution with a range tree as bmerry explains here.

It passes the 3 first subtasks but I get Memory Limit on the 2 last subtasks, though I'm using a sparse segment tree.

I store the tree with pointers (each Node has pointers to left son and right son).

I only allocate memory for a node if it is visited during an update.

If I arrive to a node which doesn't exist during a query, I don't create it, I just return 0 (because all the elements covered by this node are zeroes).

So, my memory complexity is O(logR·logC·Nu), which seems to be too big :'( Do you have a trick to reduce the ML ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский damien_g 2015-07-03 11:14:49 816 Initial revision (published)