aboutsummaryrefslogtreecommitdiff
path: root/block_placement_queries.py
diff options
context:
space:
mode:
Diffstat (limited to 'block_placement_queries.py')
-rw-r--r--block_placement_queries.py79
1 files changed, 79 insertions, 0 deletions
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]]))