ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1521. War Games 2

Optimization
Posted by Valentin Pimenov 30 Aug 2007 19:20
Should the interval tree be balanced? I use simple interval tree and get TL22.
Re: Optimization
Posted by Vedernikoff Sergey 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???
Re: Optimization
Posted by Valentin Pimenov 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.
Re: Optimization
Posted by Vedernikoff Sergey 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...
Re: Optimization
Posted by Ciprian 22 Aug 2008 11:14
I get TLE 15 with circular linked list; His trees aren't definitely good;