3161. Block Placement Queries
Hard
50 Points
Array
Binary Search
Binary Indexed Tree
Segment Tree
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:
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.
Examples
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:
Constraints
1 <= queries.length <= 15 * 1042 <= queries[i].length <= 31 <= queries[i][0] <= 21 <= 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.
3161. Block Placement Queries
Hard
50 Points
Array
Binary Search
Binary Indexed Tree
Segment Tree
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:
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.
Examples
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:
Constraints
1 <= queries.length <= 15 * 1042 <= queries[i].length <= 31 <= queries[i][0] <= 21 <= 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.