Block Placement Queries
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:
- For a query of type
1,queries[i] = [1, x]. Build an obstacle at distancexfrom the origin. It is guaranteed that there is no obstacle at distancexwhen the query is asked. - For a query of type
2,queries[i] = [2, x, sz]. Check if it is possible to place a block of sizeszanywhere 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 i^th 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]After placing an obstacle at
x = 2, a block of size at most 2 can be placed before x = 3, so the type 2 query results are false, true, and true.Example 2
Input
queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]Output
[true,true,false]After placing obstacles at
x = 7 and later x = 2, the maximum available block sizes before x = 7 become 7 and then 5, producing the shown results.Constraints
- 1 <= queries.length <= 15 * 10^4
- 2 <= queries[i].length <= 3
- 1 <= queries[i][0] <= 2
- 1 <= x, sz <= min(5 * 10^4, 3 * queries.length)
- The input is generated such that for queries of type 1, no obstacle exists at distance
xwhen the query is asked. - The input is generated such that there is at least one query of type 2.