Versioned Envelope Minimum Problem

Versioned Envelope Minimum Problem — ExecCode Hard DSA Practice

Solve the Versioned Envelope Minimum problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Each prefix of lines is one historical version of a lower envelope. Line i is y = ax + b. Contest solutions maintain those versions with a persistent Li Chao tree (or a persistent segment tree over x), while a non-persistent Li Chao / convex hull trick handles a single live envelope, and a dynamic segment tree covers a huge x-domain without allocating 4e9 slots. For each query [k, x], using only the first k lines (the prefix lines[0..k-1]), return the minimum value of ax + b. If k is 0, return 0. You are given: lines — list of [a, b] lines in insertion order queries — list of [k, x] versioned minimum queries Return one minimum per query. Later lines do not affect earlier prefixes. Ties may use any minimizing line; only the minimum value is required.

Examples

Input {'lines': [[2, 3], [-1, 10], [0, 1]], 'queries': [[1, 4], [2, 4], [3, 4], [0, 9]]}; Output [11, 6, 1, 0]. Input {'lines': [[1, 0]], 'queries': [[1, -3]]}; Output [-3]. Input {'lines': [[-2, 5], [-2, 8]], 'queries': [[2, 3]]}; Output [-1]

Constraints

Prefix k is a persistent version x may be negative k = 0 means an empty envelope

Practice Versioned Envelope Minimum free on ExecCode. Browse DSA problems, topic map, and placement guides.