Show problems as
Classic problem #3161HardArrayBinary SearchBinary Indexed TreeSegment TreeOrdered Set

Block Placement Queries

Real-world version: Rail Panel Fit Orders
Tracked in this browser only
Read Block Placement Queries on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A fabrication shop keeps a long mounting rail graduated in integer marks starting at 0. A fixed end cap is bolted at mark 0; the rest of the rail starts bare. Work arrives as orders, handled one at a time from left to right, and each entry is one of two kinds.

  • [1, x] — weld a clamp onto the rail at mark x. The clamp stays for good.
  • [2, x, sz] — a fit check. Decide whether a rigid panel of length sz could rest on the stretch of rail from mark 0 to mark x: that is, whether some integer start a exists with a >= 0 and a + sz <= x such that no clamp and not the end cap sits strictly between a and a + sz. A clamp exactly under a panel edge is fine, since the panel simply rests on it. A fit check changes nothing on the rail.

Return one boolean per fit check, in the order the checks appear in orders: true when the panel fits, false when it does not. A weld never removes a clamp, so a panel that fits at one point may stop fitting later.

Examples

Example 1

Input
orders = [[2, 6, 5], [1, 4], [2, 6, 5], [2, 6, 4]]
Output
[true, false, true]

The bare rail offers a clear run of 6 marks, so the first panel rests anywhere. Welding at mark 4 splits that run into 4 and 2, which is too little for a panel of 5 but exactly enough for one of 4.

Example 2

Input
orders = [[1, 3], [2, 9, 6], [1, 8], [2, 9, 6]]
Output
[true, false]

With one clamp at mark 3 the run from mark 3 to mark 9 measures 6, so the panel fits. The second weld at mark 8 cuts that run down to 5 and the same panel no longer fits.

Example 3

Input
orders = [[1, 4], [1, 9], [2, 9, 5], [2, 14, 5], [2, 14, 6]]
Output
[true, true, false]

Clamps at marks 4 and 9 leave runs of 4 and 5 inside the first stretch. Extending the stretch to mark 14 adds a run of 5 past the last clamp, which still tops out at 5, so a panel of 6 is refused.

Constraints

  • 1 <= orders.length <= 15 * 10^4
  • 2 <= orders[i].length <= 3
  • 1 <= orders[i][0] <= 2
  • 1 <= x, sz <= min(5 * 10^4, 3 * orders.length)
  • For an order of the first kind, no clamp is already welded at mark x
  • At least one order is a fit check

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def panel_fit_orders(orders: list[list[int]]) -> list[bool]:
Java
public List<Boolean> panelFitOrders(int[][] orders)

More on the same topics