aboutsummaryrefslogtreecommitdiff
path: root/block_placement_queries.c
diff options
context:
space:
mode:
Diffstat (limited to 'block_placement_queries.c')
-rw-r--r--block_placement_queries.c155
1 files changed, 155 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);
+}