Discussion @ 1521. War Games 2 @ Timus Online Judge

Valentin Pimenov Optimization [4] // Problem 1521. War Games 2 30 Aug 2007 19:20

Should the interval tree be balanced? I use simple interval tree and get TL22.

Vedernikoff Sergey Re: Optimization [3] // Problem 1521. War Games 2 31 Aug 2007 02:37

My program on Pascal with simple interval tree gets AC. I don't understand, what problem with C++ may you have???

Valentin Pimenov Re: Optimization [2] // Problem 1521. War Games 2 31 Aug 2007 12:45

I think the problem is in that fact that my 'simple interval tree' is not balanced. So in worst case (N=100000,K=2) I got too long tree.

Vedernikoff Sergey Re: Optimization [1] // Problem 1521. War Games 2 31 Aug 2007 22:03

Oh, if you solve it with real tree - of course, it should be balanced! My solution works with interval tree - RSQ, so it is quite fast...

Ciprian Re: Optimization // Problem 1521. War Games 2 22 Aug 2008 11:14

I get TLE 15 with circular linked list; His trees aren't definitely good;

Discussion of Problem 1521. War Games 2