Author: Ildar Gainullin Difficulty:MediumHard PreRequisites:Set Problem StatementThere is a set of points in 2D, we need to process next queries. Add/erase point in the set of points, and output the square of distance between pair of nearest points. If size of set less than 2, output 0. Initially the set is empty, coordinates of points lies in a range from 1 to 500. Subtasks 1 and 2Number of queries is less than 2500, we can store all paires squares of distances in set. Adding/erasing point into the set equivalent adding/erasing squares of distance to all points which lies in the set. After that we need to print minimal element in the set. Complexity will be $O(Q^2 log Q)$
Subtask 3We can use divideandconquer by queries to solve this problem, consider problem only with adding queries. Suppose that we are adding point $(x, y)$ into set and $ans$ is the current minimal square of distance between two points in the set, if set contains less than 2 points, assume $ans = 10^9$. We need to check only those points $(dx, dy)$, which makes new answer less than $ans$. Let's maintain for each $x$ the set of $y$  coordinates of points which has the same $x$. If we need to update answer for a point $(x, y)$, let's iterate over $dx$, and check two points(if they exists), point $(dx, dy1)$, where $dy1 >= y$ and $(dx, dy2)$, where $dy2 < y$ we can find them in $O(log 500)$ and update the answer. We don't see, if $(dx x)^2>ans$, because it has no sense to update the answer. When a number of points in the set are more then a couple of thousands, $ans$ won't be big. How to process erase queries? At first, we will solve this problem in offline, i.e initially read all queries and after that process it. At second, for each time of adding a point, let's find nearest time of erasing this point, if this point will be in the set to the end, assume that we erase it in moment of time $Q+1$, after that each point has an interval [L; R], where it is alive(i.e contains in the set). One point can have several intervals. $intervals$ contains all intervals for points. Look at the following code:
solve(L, R, intervals, ans = 1e9) {
int M = (L + R) / 2
newIntervals = []
for cint in intervals
if cint.end < L OR cint.begin > R //Point which is added in moment of time cint.begin won't be used in queries in a range from L..R, because it erased in the moment of time cint.end
continue
if cint.begin <= L AND cint.end > R //Point will be used for any query in a range L..R, we add it
AddPoint(x[cint.begin], y[cint.begin], newAns) //adding point and recalcuating ans
else: //Otherwise we will process this point somewhere deeper, number of such adding is O(R  L) in array newIntervals
newIntervals.add(cint)
if (L != R) {
solve(L, M, newIntervals, newAns)
solve(M + 1, R, newIntervals, newAns)
} else
res[L] = newAns
rollback() //rollback all changes which were done in this call of function with AddPoint
}
solve(1, Q, 1e9)
Total complexity of this algorithm is $O(Q * log Q * 500 * log 500)$ but with very small constant. Solution:Setter's solution can be found here Please feel free to post comments if anything is not clear to you.
This question is marked "community wiki".
asked 29 Apr '17, 21:15

Please tag ltime47 and editorial so that this post is visible from the link given on the contest page. answered 30 Apr '17, 04:41
