CIELWEB - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

This problem can be solved by using segment tree with O(M2 + (N+Q) log N) time.

For each node in the segment tree denotes a interval of Ciel’s restaurants. Let’s focus on the node c corresponding from **x-**th to y-th Ciel’s restaurants. And let node c have the following values:

  • COST1[c] : which denotes the sum of 2 * C[TOWERk] * |Y[TOWERk] - Xk| overall x ≤ k ≤ y (or infinity if some restaurants have no available towers)
  • COST2[c] : which denotes the sum of UTYPE[k], TYPE[k+1] for all x ≤ k < y, TOWERk ≠ TOWERk+1
  • LEFT[c] : which denotes TOWERx
  • RIGHT[c] : which denotes TOWERy

Then we can calculate the these 4 values for any interval i with O(N log N) time. And the cost of the communication between the LEFT[i]-th and RIGHT[i]-th restaurants is calculated as COST1[i] + COST2[i] - C[TOWERLEFT[i]]* |Y[TOWERLEFT[i]] - XLEFT[i]| - C[TOWERRIGHT[i]] * |Y[TOWERRIGHT[i]] - XRIGHT[i].

Next, when a tower information is given, we need to update the segment tree. At first, we can check which an interval of the restaurants use this tower by binary search with O(N log N). Let [a, b] be interval in which the restaurants use the tower and the coordinates of the restaurants are less than the tower’s coordinate. And let [c, d] be interval in which the restaurants use the tower and the coordinates of the restaurants are no less than the tower’s coordinate. That is, let k be in the interval [a, b], then |Xk - Y| ≤ R and Xk < Y.

Then we update for these 2 intervals. In order to update for the interval [a, b], it seems we need to change all nodes whose interval has an intersection with [a, b]. However the number of such nodes can be large such as N log N, so it is too slow. Therefore we don’t update the descendants of the nodes whose interval completely contains [a, b], until the descendant is unused for calculating a communication cost. The node whose interval doesn’t contains [a, b] can be updated from its updated children, and the node whose interval contains [a, b] can be updated such that

COST1 = (the number of restaurants in the node) * Y - (the sum of coordinates of restaurants in the node)

COST2 = 0

LEFT = RIGHT = the new tower.

In this case, the number of the nodes which we should update is O(log N).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.