How to solve YATP from Kattis?

Правка en1, от szawinis, 2017-03-18 12:32:35

Problem Statement: Click

It definitely requires convex hull optimization, but I'm not sure how to merge the sets properly. I've thought about the usual "merge the small subtree to the large subtree" trick, but it doesn't seem to work. Is there anything I'm missing? And also, which variant of the convex hull optimization should I use? Does it require the fully dynamic variant?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский szawinis 2017-03-18 12:32:35 452 Initial revision (published)