diff options
Diffstat (limited to 'block_placement_queries.py')
-rw-r--r-- | block_placement_queries.py | 79 |
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]])) |