Return to Question

You are given a list of (a,b), and a list of x. Compute the maximum ax+b for each x. You can assume a, b and x are non-negative integers.

Your program or function must run in expected (to the randomness if your code involves that, not the input) O(nlogn) time where n is the total input length (sum or maximum of the lengths of both lists).

This is code-golf. Shortest code wins.

###Example

[[2 8] [4 0] [2 1] [1 10] [3 3] [0 4]] [1 2 3 4 5]

Output:

[11 12 14 16 20]

Explanation:

11 = 1*1 + 10
12 = 1*2 + 10 = 2*2 + 8
14 = 2*3 + 8
16 = 2*4 + 8 = 4*4 + 0
20 = 4*5 + 0

###Note about the complexity:

If you used a builtin having a good average-case complexity, and it can be randomized to get the expected complexity easily in theory, you can assume your language did that.

That means, if your program can be tested to be O(nlogn) (in theory), with edge cases for your code, but not the implementation of your language, we'll say it is O(nlogn).

You are given a list of (a,b), and a list of x. Compute the maximum ax+b for each x. You can assume a, b and x are non-negative integers.

Your program or function must run in expected (to the randomness if your code involves that, not the input) O(nlogn) time where n is the total input length (sum or maximum of the lengths of both lists).

This is code-golf. Shortest code wins.

###Example

[[2 8] [4 0] [2 1] [1 10] [3 3] [0 4]] [1 2 3 4 5]

Output:

[11 12 14 16 20]

Explanation:

11 = 1*1 + 10
12 = 1*2 + 10 = 2*2 + 8
14 = 2*3 + 8
16 = 2*4 + 8 = 4*4 + 0
20 = 4*5 + 0

###Note about the complexity:

If you used a builtin having a good average-case complexity, and it can be randomized to get the expected complexity easily in theory, you can assume your language did that.

That means, if your program can be tested to be in O(nlogn), possibly with edge case exceptions because of the implementation of your language, but cannot be seen logically in your own code, we'll say it is O(nlogn).