aboutsummaryrefslogtreecommitdiff
path: root/block_placement_queries.c
blob: 3f244ed769eebbca1ba15941ea74c7fdf9f1db61 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
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);
}