The cheapest plan
A service compares tariff plans. A plan has a monthly fee of a tenge and a price of b tenge per unit of usage: at usage x a month costs a + b · x. Plans appear one at a time, mixed with questions “how much will a person with usage x pay for a month if they choose the cheapest of the plans that have appeared so far?”.
Input
The first line holds the number of events q (1 ≤ q ≤ 10⁵). Then q lines: add a b, a plan has appeared (0 ≤ a ≤ 10⁹, 0 ≤ b ≤ 10⁶), or ask x, a question (0 ≤ x ≤ 10⁶).
Output
For each question, the lowest cost of a month, or - if there are no plans yet.
Examples
Example 1
8 ask 5 add 2000 30 ask 100 add 5000 5 ask 100 ask 200 add 0 60 ask 50
- 5000 5000 6000 3000
Example 2
4 add 100 10 add 100 10 ask 0 ask 1000000
100 10000100
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A plan is a line y = a + bx, and the answer is the lower envelope of the lines at the point x. Why will the deque from the article not do here?
2Hint 2
Slopes arrive in any order, and questions come at any points and mixed with new plans. You need a structure where a line can be added at any moment and the minimum at a point found in a logarithm. The points x are integers from 0 to 10⁶.
3The idea
A Li Chao tree over the range [0, 2²⁰). A node keeps the line that is lower at the middle of its range. Two lines intersect at most once, so the line that lost at the middle can win only on one half, and that is where it goes down. The answer at a point is the minimum of the lines on the path from the root to the leaf.
4Walkthrough
The tree is arrays of 2 · 2²⁰ nodes, as in a segment tree with root 1. Insertion: if the node is empty, put the line there; otherwise compare at the middle and swap if the new one is lower; then look at the ends of the range: wherever the loser is lower, go down there, and if at neither end, it is not needed anywhere. A question: go to leaf x while the nodes are not empty, and take the minimum.
4+Solution
5Complexity
O(log C) per event, C = 2²⁰: twenty levels. A cost is at most 10⁹ + 10¹², which fits in 64 bits.
6Common mistakes
- Trying all plans. This is
wrong.py: with fifty thousand plans and as many questions it is more than a billion multiplications, and in the third test the time runs out. - A deque with sorted slopes. Plans arrive mixed with questions and cannot be sorted in advance.
- Comparing at the wrong point. The direction to go down must be decided by the ends of the node's range (or by the sign of the difference at the middle and at one end), otherwise the losing line goes into the wrong half.
- An empty tree. A question before the first plan is
-, not zero and not “infinity”.