CHTPRAC - CHT Practice
You can test you CHT implementation in this problem. Problem is simple. You have to solve some queries in the form -
- 1 m b: Add a function f(x) = mx + b in a set.
- 2 x: For all existing functions in the set, find the maximum/minimum value of { fi(x)) }.
You also have some special constriants on the inputs. In a dataset, you have either of the four cases for all queries -
- mi > mi+1, and all queries are for minimum.
- mi > mi+1, and all queries are for maximum.
- mi < mi+1, and all queries are for minimum.
- mi < mi+1, and all queries are for maximum.
Furthermore, all queries of second kind will obey this - xi < xi+1.
Input
In the first line, you will have a number Q <= 10^5, the number of queries. Then a integer a, where a denotes the case number (from problem statement), which you'll need to handle in this dataset.
Next Q lines will contain a number t first, if it is 1 then another two integers will be given m b, where |m|, |b|<= 10^9. Then you need to add the function f(x) = mx + b into set.
if t is 2, then you will be given a number |x| <= 10^9, you need to answer the query as described.
Output
For each query of second type, print the desired answer in a seperate line.
Example
Input: 5 1
1 5 1
1 4 -1
1 3 -2
2 -1
2 3 Output:
-5
7
Added by: | Rezwan |
Date: | 2018-03-02 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |