Блог пользователя damien_g

Автор damien_g, история, 9 лет назад, По-английски

Hello Codeforces!

I just got a mail from my leader this morning, which says that the IOI 2013 syllabus will be used at IOI 2015.

It's explained in this note in misof's syllabus page.

So, explicitly excluded topics in the IOI 2013 syllabus won't be needed, essentially:

  • max flow and bipartite matching algorithms

  • implementation of any general balanced tree (e.g., AVL, treaps, splay trees)

Hope it helps!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

Автор damien_g, история, 9 лет назад, По-английски

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 ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится