0130HardArrayBinary SearchBinary Indexed TreeSegment TreeOrdered Set

Rail Panel Fit Orders

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def panel_fit_orders(orders: list[list[int]]) -> list[bool]:

Java

public List<Boolean> panelFitOrders(int[][] orders)

The intended approach

Time O((n + M) log M) where n is the number of orders and M the largest markSpace O(M)

A panel of length `sz` fits inside `[0, x]` exactly when some clear run there is at least `sz` long, where the runs are the gaps between neighbouring clamps plus the tail from the last clamp at or before `x` up to `x` itself. Keep the length of the run ending at each clamped mark in a segment tree keyed by mark, so a fit check is a prefix maximum over marks `0..x` compared with the tail. A weld at mark `m` only touches two runs: the new one ending at `m`, and the one ending at the next clamp after `m`, which shortens. Two more max/min trees over clamped marks supply the neighbouring clamps, so each order costs a logarithmic number of steps.

Pythonentry point: panel_fit_orders

def panel_fit_orders(orders):
    limit = 1
    for order in orders:
        if order[1] > limit:
            limit = order[1]
    size = 1
    while size <= limit:
        size <<= 1
    far = limit + 1
    # stretch[m] holds the length of the clear run that ends at clamped mark m
    stretch = [0] * (2 * size)
    # newest[r] is the greatest clamped mark inside r, oldest[r] the smallest
    newest = [-1] * (2 * size)
    oldest = [far] * (2 * size)

    def set_stretch(mark, value):
        node = mark + size
        stretch[node] = value
        node >>= 1
        while node:
            a = stretch[2 * node]
            b = stretch[2 * node + 1]
            stretch[node] = a if a > b else b
            node >>= 1

    def add_clamp(mark):
        node = mark + size
        newest[node] = mark
        oldest[node] = mark
        node >>= 1
        while node:
            a = newest[2 * node]
            b = newest[2 * node + 1]
            newest[node] = a if a > b else b
            a = oldest[2 * node]
            b = oldest[2 * node + 1]
            oldest[node] = a if a < b else b
            node >>= 1

    def widest_stretch(hi):
        best = 0
        lo_node = size
        hi_node = hi + size + 1
        while lo_node < hi_node:
            if lo_node & 1:
                if stretch[lo_node] > best:
                    best = stretch[lo_node]
                lo_node += 1
            if hi_node & 1:
                hi_node -= 1
                if stretch[hi_node] > best:
                    best = stretch[hi_node]
            lo_node >>= 1
            hi_node >>= 1
        return best

    def clamp_at_or_before(hi):
        found = -1
        lo_node = size
        hi_node = hi + size + 1
        while lo_node < hi_node:
            if lo_node & 1:
                if newest[lo_node] > found:
                    found = newest[lo_node]
                lo_node += 1
            if hi_node & 1:
                hi_node -= 1
                if newest[hi_node] > found:
                    found = newest[hi_node]
            lo_node >>= 1
            hi_node >>= 1
        return found

    def clamp_at_or_after(lo):
        found = far
        if lo > limit:
            return found
        lo_node = lo + size
        hi_node = limit + size + 1
        while lo_node < hi_node:
            if lo_node & 1:
                if oldest[lo_node] < found:
                    found = oldest[lo_node]
                lo_node += 1
            if hi_node & 1:
                hi_node -= 1
                if oldest[hi_node] < found:
                    found = oldest[hi_node]
            lo_node >>= 1
            hi_node >>= 1
        return found

    add_clamp(0)  # the fixed end cap
    verdicts = []
    for order in orders:
        if order[0] == 1:
            mark = order[1]
            before = clamp_at_or_before(mark - 1)
            set_stretch(mark, mark - before)
            after = clamp_at_or_after(mark + 1)
            if after <= limit:
                set_stretch(after, after - mark)
            add_clamp(mark)
        else:
            edge = order[1]
            length = order[2]
            best = widest_stretch(edge)
            tail = edge - clamp_at_or_before(edge)
            if tail > best:
                best = tail
            verdicts.append(best >= length)
    return verdicts

The obvious version

Keeps clamps in a plain set and answers each fit check by literally trying every integer start position, scanning the clamps to see whether any of them falls strictly inside the panel. No notion of runs or prefix maxima, so it agrees with the statement rather than with the insight.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_panel_fit_orders(orders):
    clamps = {0}
    verdicts = []
    for order in orders:
        if order[0] == 1:
            clamps.add(order[1])
        else:
            edge = order[1]
            length = order[2]
            fits = False
            for start in range(0, edge - length + 1):
                blocked = False
                for mark in clamps:
                    if start < mark < start + length:
                        blocked = True
                        break
                if not blocked:
                    fits = True
                    break
            verdicts.append(fits)
    return verdicts

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in