diff options
-rw-r--r-- | block_placement_queries.c | 155 | ||||
-rw-r--r-- | block_placement_queries.py | 79 |
2 files changed, 234 insertions, 0 deletions
diff --git a/block_placement_queries.c b/block_placement_queries.c new file mode 100644 index 0000000..3f244ed --- /dev/null +++ b/block_placement_queries.c @@ -0,0 +1,155 @@ +// 3161. Block Placement Queries +#include "leetcode.h" + +/* + * there exists an infinite number line, with its origin at 0 and extending + * towards the positive x-axis. you are given a 2d array 'qeuries', which + * contains two types of queries: 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. for query 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 a block specified in + * the i'th query of type 2, and false otherwise. + */ + +struct segment_tree { + int *tree; + int *max; + int size; +}; + +struct segment_tree *segment_tree_init(int size) { + struct segment_tree *obj = + (struct segment_tree *)malloc(sizeof(struct segment_tree)); + obj->size = size; + obj->tree = (int *)malloc(size * sizeof(int)); + obj->max = (int *)malloc(size * sizeof(int)); + for (int i = 0; i < size; i++) { + obj->tree[i] = -1; + obj->max[i] = -1; + } + return obj; +} + +void segment_tree_update(struct segment_tree *obj, int idx) { + int tmp = 0, max = 0, start = 0; + if (obj->tree[idx] != -1) { + start = idx; + max = obj->max[idx]; + } else { + for (int i = idx; i >= 0; i--) { + if (obj->tree[i] != -1) { + start = i; + max = obj->max[i]; + break; + } + } + } + obj->tree[idx] = -2; + for (int i = start; i < idx; i++) { + if (obj->tree[i] == -1) + obj->tree[i] = tmp; + if (tmp > max) + max = tmp; + tmp++; + if (obj->tree[i] == -2) + tmp = 1; + obj->max[i] = max; + } + if (tmp > max) + max = tmp; + obj->max[idx] = max; + for (int i = idx + 1; i < obj->size; i++) { + if (obj->tree[i] == -1) + break; + if (obj->max[i] == max && (obj->tree[i] == -2 || obj->tree[i] == max)) + break; + if (obj->tree[i] == -2) { + if (tmp > max) + max = tmp; + tmp = 0; + + } else + obj->tree[i] = tmp; + if (tmp > max) + max = tmp; + tmp++; + obj->max[i] = max; + } +} + +int segment_tree_query(struct segment_tree *obj, int end, int size) { + if (end - size < 0) + return 0; + for (int i = end; i >= 0; i--) { + if (end - i >= size) + return size; + if (obj->tree[i] != -1) + return obj->max[i]; + } + return 0; +} + +bool is_intersected(struct segment_tree *obj, int end, int size) { + if (end - size < 0) + return false; + int max = segment_tree_query(obj, end, size); + return max >= size; +} + +bool *getResults(int **queries, int queriesSize, int *queriesColSize, + int *returnSize) { + *returnSize = 0; + int tree_size = 0; + for (int i = 0; i < queriesSize; i++) { + if (tree_size < queries[i][1]) + tree_size = queries[i][1]; + if (queriesColSize[i] == 3 && queries[i][0] == 2) + (*returnSize)++; + } + tree_size++; + bool *ans = (bool *)malloc(*returnSize * sizeof(bool)); + struct segment_tree *tree = segment_tree_init(tree_size); + int idx = 0; + for (int i = 0; i < queriesSize; i++) { + int m = queriesColSize[i], *curr = queries[i]; + if (m == 2 && curr[0] == 1) { + int val = curr[1]; + segment_tree_update(tree, val); + } else if (m == 3 && curr[0] == 2) { + int end = curr[1], size = curr[2]; + ans[idx++] = is_intersected(tree, end, size); + } + } + free(tree->tree), free(tree); + return ans; +} + +int main() { + int q1i[4][3] = {{1, 2}, {2, 3, 3}, {2, 3, 1}, {2, 2, 2}}, qcs1[] = {}, rs1; + int q2i[5][3] = {{1, 7}, {2, 7, 6}, {1, 2}, {2, 7, 5}, {2, 7, 6}}, + qcs2[] = {}, rs2; + for (int i = 0; i < ARRAY_SIZE(q1i); i++) + qcs1[i] = ARRAY_SIZE(q1i[i]); + for (int i = 0; i < ARRAY_SIZE(q2i); i++) + qcs2[i] = ARRAY_SIZE(q2i[i]); + struct two_d_arr q1, q2; + two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i); + two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i); + bool *gr1 = getResults(q1.arr, q1.row_size, qcs1, &rs1); + bool *gr2 = getResults(q2.arr, q2.row_size, qcs2, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", gr1[i]); // expect: 0 1 1 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", gr1[i]); // expect: 1 1 1 + printf("\n"); + free(gr1); + free(gr2); + two_d_arr_free(&q1); + two_d_arr_free(&q2); +} diff --git a/block_placement_queries.py b/block_placement_queries.py new file mode 100644 index 0000000..21e8b86 --- /dev/null +++ b/block_placement_queries.py @@ -0,0 +1,79 @@ +# 3161. Block Placement Queries +from sortedcontainers import SortedList +from itertools import pairwise +from bisect import bisect_right + +""" +there exists an infinite number line, with its origin at 0 and extending +towards the positive x-axis. you are given a 2d array 'qeuries', which +contains two types of queries: 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. for query 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 a block specified in +the i'th query of type 2, and false otherwise. +""" + + +class tree: + def __init__(self, n): + self.n = n + self.l = [0] * (n + 1) + + def add(self, i, x): + i += 1 + while i <= self.n: + self.l[i] = max(self.l[i], x) + i += i & -i + + def query(self, i): + i += 1 + ans = 0 + while i: + ans = max(ans, self.l[i]) + i -= i & -i + return ans + + +class Solution(object): + def getResults(self, queries): + """ + :type queries: List[List[int]] + :rtype: List[bool] + """ + list = SortedList() + n = min(5 * 10**4, len(queries) * 3) + list.add(0) + list.add(n) + for i in queries: + if i[0] == 1: + curr = i[1] + list.add(curr) + bit, ans = tree(n + 1), [] + for i, j in pairwise(list): + bit.add(j, j - i) + for i in reversed(queries): + if i[0] == 1: + curr = i[1] + idx = list.index(curr) + post = list[idx + 1] + prev = list[idx - 1] + list.remove(curr) + bit.add(post, post - prev) + else: + _, curr, size = i + idx = list.bisect_right(curr) + prev = list[idx - 1] + ans.append(bit.query(prev) >= size or (curr - prev) >= size) + ans.reverse() + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.getResults(queries=[[1, 2], [2, 3, 3], [2, 3, 1], [2, 2, 2]])) + print(obj.getResults(queries=[[1, 7], [2, 7, 6], [1, 2], [2, 7, 5], [2, 7, 6]])) |