PROBLEM LINK:Author: Full name Tester: Full name Editorialist: Oleksandr Kulkov DIFFICULTY:MEDIUMHARD PREREQUISITES:Convex hull trick, segment tree PROBLEM:There are $n$ pizzerias located on positions $s_i$ and $m$ customers located on positions $c_i$. All pizzerias have distinct positions. Delivering pizza from point $x_1$ to point $x_2$ costs $(x_1x_2)^2$, additionally each pizzeria has value $p_i$ such that all pizza from that pizzeria cost additionaly $p_i$. For each customer you have a list of pizzerias such that this customer won't order from those pizzerias. You have to find for each customer amount of money they will spend for pizza delivery. QUICK EXPLANATION:You can assume that deletion of some pizzeria will lead to splitting of pizzeria set into $k+1$ continuous subsets, which you can compute independently using segment tree. You should also note that inside subset it's simply minimization of linear functions, thus you can build convex hull of corresponding linear functions in each vertex of segment tree. EXPLANATION:First of all we should note that to deliver pizza from $i$th pizzeria to any position $x$ we will have to pay $p_i+(s_ix)^2 = (p_i+s_i^2)2s_i \cdot x+x^2$. Since coefficient near $x^2$ is $1$ for all pizzerias we can ignore $x^2$ part at all and assume that we're dealing with linear functions of cost: $f_i(x) = (p_i+s_i^2)2s_i \cdot x$. If $k=0$ for all queries we just have to find linear function with minimum value for set of points. Thus we certainly look for some modification of convex hull trick. To do this we should note that deletion of $k$ pizzerias split array $f_1(x),\dots,f_n(x)$ into $k+1$ subarrays. Now to find minimum possible value among remaining functions we can find it in each of these segments and return the minimum among these numbers. To answer such queries in segments we can maintain segment tree having lower envelope of functions which are met in segment of vertex. Please refer to authors solution and some tutorials on convex hull trick and mergesort tree to understand basic concepts behind the solution. Suggested resources: Convex Hull Trick, MergeSort tree ("Saving the entire subarrays in each vertex" section). ALTERNATIVE SOLUTIONS:You can directly find $k+1$ functions having minimum value in given point if you consider function $a_i \cdot x + b_i$ as point $(a_i;b_i)$ and instead of $k+1$ functions having minimum value in $c_i$ you will have to find $k+1$ points having minimum scalar product with point $(c_i;1)$. To do this you will have to build convex layers of given points and do stuff like described here. This is much harder than original solution though. Also you may use sqrtdecomposition instead of segment tree. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here.
This question is marked "community wiki".
asked 18 Jul '18, 06:35

My solution: for k>sqrt(n) just check all pizzerias. I did convex hull trick sqrt(n) times, removing the minimum envelope. Then I answered queries offline with k<sqrt(n) for each i checked lowest k+1 envelopes. answered 20 Jul '18, 04:02

Somebody please give reference from where Convex Hull Trick can be learnt. answered 21 Jul '18, 18:54
https://wcipeg.com/wiki/Convex_hull_trick
(22 Jul '18, 00:07)
Thank you :)
(22 Jul '18, 20:21)
