3161. Block Placement Queries Hard

1/**
2 * [3161] Block Placement Queries
3 *
4 * There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis.
5 * You are given a 2D array queries, which contains two types of queries:
6 * <ol>
7 * 	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.
8 * 	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.
9 * </ol>
10 * 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.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]</span>
15 * Output: <span class="example-io">[false,true,true]</span>
16 * Explanation:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2024/04/22/example0block.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 309px; height: 129px;" />
18 * For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3.
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">queries = </span>[[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]<!-- notionvc: 4a471445-5af1-4d72-b11b-94d351a2c8e9 -->
23 * Output: [true,true,false]
24 * Explanation:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2024/04/22/example1block.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 310px; height: 130px;" />
26 * 
27 * 	Place an obstacle at x = 7 for query 0. A block of size at most 7 can be placed before x = 7.
28 * 	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.
29 * </div>
30 *  
31 * Constraints:
32 * 
33 * 	1 <= queries.length <= 15 * 10^4
34 * 	2 <= queries[i].length <= 3
35 * 	1 <= queries[i][0] <= 2
36 * 	1 <= x, sz <= min(5 * 10^4, 3 * queries.length)
37 * 	The input is generated such that for queries of type 1, no obstacle exists at distance x when the query is asked.
38 * 	The input is generated such that there is at least one query of type 2.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/block-placement-queries/
44// discuss: https://leetcode.com/problems/block-placement-queries/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn get_results(queries: Vec<Vec<i32>>) -> Vec<bool> {
50        vec![]
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_3161() {
62    }
63}
64