Skip to content

3435. Block Placement Queries

Array Binary Search Binary Indexed Tree Segment Tree

Problem - Block Placement Queries

Hard

There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis.

You are given a 2D array queries, which contains two types of queries:

  1. For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked.
  2. For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate.

Return a boolean array results, where results[i] is true if you can place the block specified in the ith query of type 2, and false otherwise.

 

Example 1:

Input: queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]

Output: [false,true,true]

Explanation:

For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3.

Example 2:

Input: queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]

Output: [true,true,false]

Explanation:

  • Place an obstacle at x = 7 for query 0. A block of size at most 7 can be placed before x = 7.
  • Place an obstacle at x = 2 for query 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2.

 

Constraints:

  • 1 <= queries.length <= 15 * 104
  • 2 <= queries[i].length <= 3
  • 1 <= queries[i][0] <= 2
  • 1 <= x, sz <= min(5 * 104, 3 * queries.length)
  • The input is generated such that for queries of type 1, no obstacle exists at distance x when the query is asked.
  • The input is generated such that there is at least one query of type 2.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Tree:
    def __init__(self, n: int):
        self.tree = [0] * (n + 1)

    def maximize(self, i: int, val: int):
        while i < len(self.tree):
            self.tree[i] = max(self.tree[i], val)
            i += Tree.lowtree(i)

    @staticmethod
    def lowtree(i: int) -> int:
        return i & -i

    def get(self, i: int) -> int:
        result = 0
        while i > 0:
            result = max(result, self.tree[i])
            i -= Tree.lowtree(i)
        return result

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        n = len(queries) * 3
        result = []
        tree = Tree(n + 1)
        obsticles = SortedList([0, n])

        for query in queries:
            if query[0] == 1:
                obsticles.add(query[1])

        for val1, val2 in pairwise(obsticles):
            tree.maximize(val2, val2 - val1)

        for query in reversed(queries):
            if query[0] == 1:
                val = query[1]
                i = obsticles.index(val)
                next_val = obsticles[i + 1]
                last_val = obsticles[i - 1]
                obsticles.remove(val)
                tree.maximize(next_val, next_val - last_val)
            else:
                val = query[1]
                sz = query[2]
                i = obsticles.bisect_right(val)
                last_val = obsticles[i - 1]
                result.append(tree.get(last_val) >= sz or val - last_val >= sz)

        return result[::-1]

Submission Stats:

  • Runtime: 3373 ms (57.72%)
  • Memory: 76.2 MB (97.14%)