PeterNaut's blog

How hard is it to implement an interval tree?
By PeterNaut, 10 years ago, In English

Is it wise and feasible to implement an interval tree in a Codeforces round (two hours long)? What about in a 5 hour long contest (ioi)?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Segment tree with point update and interval query is very simple data structure. It can be implemented in 5-10 minutes during the round. You can take a look at problem C from rounds 223 and 225 for examples of the solution.

→ Reply
»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

In my opinion, if you want to get a high score on the IOI, you must implement it easily within 15-20 minutes(basic operatios: adding on the interval/sum/max/min and etc.). I'm sure you won't have problems with that if you practise coding it.

→ Reply