aboutsummaryrefslogtreecommitdiff
path: root/block_placement_queries.py
blob: 21e8b86811977eb6416e308af8413ff2e97b4564 (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
# 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]]))