Intuitive, quick read, Binary Search solution
Intuition and approach\nFor each query of type 2, we want to find out whether or not there is space for block of length sz up to distance x. So we need to check
# Intuition and approach\nFor each query of type 2, we want to find out whether or not there is space for block of length $$sz$$ up to distance $$x$$. So we need to check all of the walls already placed up to $$x$$ and find the maximum gap or see if the gap between $$x$$ and the last wall to the left is large enough for the block.\n\nThe most obvious way to do this is to store the locations of the walls in order and check the gap between each one. This would mean $$O(n)$$ time to check the walls.\n\nSince we have them in order, we can find the last wall using binary search in $$O(log(n))$$ time, but the gap can appear before this wall so we will need to store the largest gap to the left with the wall. Then when we insert a new wall we will need to update the max gap for walls after only while this gap was the one used as the max, which is constant time complexity assuming that wall gaps increase with wall placements.\n\nNow we can do type 2 queries in $$O(log(n))$$ time because we just need to perform binary search and check if the block fits, but type 1 queries still take $$O(n)$$ time because of python list insertion.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$ <br>\n$$O(n)$$ iterate through queries\n    - $$O(log(n))$$ find location of wall to the left using binary search\n    - Type 1:\n    $$O(n)$$ list insertion\n    $$O(1)$$ update all values to right that could have been using the updated gap as their longest gap before. Time complexity calculated assuming that wall gaps increase with distance from origin\n    - Type 2:\n    $$O(1)$$ calculation of distance to wall to left and lookup of previous largest gap used to check if block can fit\n    $$O(1)$$ append value to results\n\n\n- Space complexity:\n$$O(n)$$ for w (array with wall locations and max gap to the left)\n\n# Code with comments\n```\nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        # w[i] = [ wall location, largest gap to the left ]\n        # Adding the zero wall means we do not have to worry about\n        # this edge case.\n        w = [[0, 0]]\n        r = []\n        for q in queries:\n            # Binary search\n            i = 0\n            j = len(w) - 1\n            while i < j:\n                k = math.ceil((i+j)/2)\n                # A block may touch an obstacle, therefore if a wall\'s\n                # location is equal to x then we do not consider\n                # it. We also do not need it for insertion as "there\n                # is no obstacle at distance x when the query is\n                # asked".\n                if w[k][0] >= q[1]:\n                    j = k - 1\n                else:\n                    i = k\n            match q[0]:\n                case 1:\n                    # Insert new wall\n                    w.insert(i + 1, [q[1], 0])\n                    # Update new wall with correct max gap value:\n                    # max of new gap and left wall max gap.\n                    w[i+1][1] = max(w[i][1], w[i+1][0] - w[i][0])\n                    i += 1\n                    # Wall to right must be checked\n                    if i + 1 < len(w):\n                        w[i+1][1] = max(w[i][1], w[i+1][0] - w[i][0])\n                        i += 1\n                    # Only subsequent walls to right that have larger\n                    # gaps than the current largest gap and do not use\n                    # the gap between themselves and previous need to\n                    # be updated. Once this is no long satisfied, no\n                    # walls to the right need to be updated.\n                    while i+1 < len(w) and w[i][1] < w[i+1][1] and w[i+1][0] - w[i][0] < w[i+1][1]:\n                        w[i+1][1] = max(w[i][1], w[i+1][0] - w[i][0])\n                        i += 1\n                case 2:\n                    # Take max of gap between x and left wall and max\n                    # gap to left stored in w[left wall index].\n                    d = max(q[1] - w[i][0], w[i][1])\n                    r.append(d >= q[2])\n        return r\n```
['Binary Search', 'Python3']