Editorial for IOI '18 P6 - Meetings
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
If a meeting place is given, you can calculate the cost of a meeting in . Thus, by testing every possible meeting place, the cost of a meeting can be calculated in time.
The total time complexity is .
Subtask 2
By iterating through the mountains with maintaining an upper envelope, you can get costs for all meeting places in time.
The total time complexity is .
Subtask 3
Find the longest contiguous subsequence consisting only of by SegmentTree. The total time complexity is .
Subtask 4
For each meeting, divide the range at the highest mountains and recursively solve the problem.
If you pre-calculate the answer to some ranges, such as maximal ranges in which heights of all mountains are at most some constant, and you prepare a proper data structure for Range Minimum Queries, you can get the minimum cost of a meeting in time.
Pre-calculation can be done in time.
The total time complexity is .
Subtask 5
For convenience, let's assume that all values of are distinct (this does not matter much). For each meeting, we can assume that the index of the optimal meeting place is greater than or equal to , because by reversing the array and solving the same problem we can get a real answer.
We denote the problem of calculating the minimum cost of a meeting with the range as query .
- Let be the answer to the query .
- Let be the smallest such that .
- Similarly, let be the largest such that .
- Also, let be the array of length
such that the () value of is
We are going to compute for all , and then it is easy to get answers to all queries. The order of indices in which we compute is very important. Here, we use depth-first-search post-order of the cartesian tree of .
We define the cartesian tree of as the rooted tree such that the lowest-common-ancestor of nodes and is the node .
The cartesian tree can be obtained in linear time by an iteration with a stack data structure. It can be easily seen that every node of the cartesian tree has at most two children, one to the left and another to the right. Let be the left child of the node and be the right child of the node (here we assume that the node has two children).
Now the remaining task is to somehow merge and into . Clearly, first some elements of is exactly .
All we need is to compute , for all ().
Since is the maximum value in the range , you can see
and
where .
The inequality follows from the observation that
It indicates that there exists a certain index such that
for all , and
for all .
Therefore, you can get in the following way:
- Let be the array obtained by adding a certain value to all elements of .
- Update first some elements of with a certain linear function.
- Concatenate , , and .
To carry out these operations fast, we use a compressed representation for . is represented by the list of ranges. Each range has a certain linear function such that the values of in the range can be calculated by the linear function.
Adding a certain value can be done by lazy propagation.
To update first some elements, we simply iterate through from the beginning. The ranges before the break point are replaced by one range, so the total number of iterations is .
Concatenating two arrays can be done as follows:
- We maintain end points of ranges in a global set and store the information of ranges in a global array. Then, we do not have to do anything for ranges.
- Concatenating lazy propagation information for adding can be done by Weighted-union heuristic:
- Let be the value which should be added to elements of the array .
- When we concatenate two arrays and , we pick the smaller one and arrange the elements of it so that .
- By Weighted-union heuristic, this can be done in time in total.
Getting the answer to a query requires one lower bound operation of the set. Thus in time we can get answers to all queries.
The total time complexity is .
Comments