aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--block_placement_queries.c155
-rw-r--r--block_placement_queries.py79
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]]))