Best Pair Above the Bars

Hard

A game has n items: item j has speed speed[j] and power power[j]. Its overall value is speed[j] + power[j]. You are given a list of asks asks, where asks[i] = [x, y]. For an ask, find the item with speed at least x and power at least y whose overall value is the largest, and return that value. If no item qualifies, the answer to the ask is -1. Return the answers in the order of the asks. Scanning every item for every ask is too slow.

Example 1

speed=[5, 2, 8, 3], power=[1, 7, 4, 6], asks=[[3, 2], [1, 6], [6, 5]] → [12, 9, -1]

Ask [3, 2]: items 2 (8 + 4 = 12) and 3 (3 + 6 = 9) qualify, so 12. Ask [1, 6]: items 1 (9) and 3 (9), so 9. Ask [6, 5]: no item has speed ≥ 6 and power ≥ 5 at once, so -1.

Example 2

speed=[4, 4], power=[4, 9], asks=[[4, 4], [5, 1]] → [13, -1]

Both items fit the first ask and the better one gives 13; nothing fits the second.

Constraints

1 ≤ n = len(speed) = len(power) ≤ 10⁵
1 ≤ speed[j], power[j] ≤ 10⁹
1 ≤ len(asks) ≤ 10⁵
1 ≤ x, y ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Binary Indexed Tree Segment Tree Array Binary Search Sorting Monotonic Stack

Similar problems

First Common Rooftop Hard Second Larger to the Right Hard Deal Out From the Lowest Card Hard Smaller Values to the Right Hard Window Sums Within a Band Hard

Input

speed=[5, 2, 8, 3], power=[1, 7, 4, 6], asks=[[3, 2], [1, 6], [6, 5]]

Expected

[12, 9, -1]

Run checks the first 3 tests in your browser. Submit checks all 66 tests on the server, hidden ones included.