Python | 2 SortedLists, no segment tree | O(nlogn) | Beats 100%
Intuition\nThe problem requires efficient handling of two types of queries: adding a barrier and checking if a hole of a certain size can fit starting from a sp
# Intuition\nThe problem requires efficient handling of two types of queries: adding a barrier and checking if a hole of a certain size can fit starting from a specific position. To manage the barriers dynamically and find holes efficiently, we can use sorted lists.\n\n# Approach\n1. Use a `SortedList` to maintain the positions of the barriers.\n2. Use another `SortedList` to manage the sizes of the holes.\n3. Process queries in direct order to fill barriers:\n   - For add-barrier queries, add barriers to the `SortedList`.\n4. Initialize hole sizes based on the filled barriers list.\n5. Process queries in reverse order:\n   - For the add-barrier query:\n     - Remove the barrier from the sorted list.\n     - Update the hole sizes based on the new barrier position.\n   - For the check-hole query:\n      - Use binary search to find the smallest hole that is at least as large as the required size.\n      - Check if the start position of this hole allows the hole to fit within the specified constraints.\n# Complexity\n- Time complexity:\n  - Adding a barrier: O(log n) due to insertion into a sorted list.\n  - Checking a hole: O(log n) due to binary search on the hole   sizes.\n  - Overall complexity is O(n * log n).\n- Space complexity:\n  - O(n)\n\n# Code\n```\nfrom sortedcontainers import SortedList\n\n\nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        barriers = SortedList()  # Sorted list to maintain barrier positions\n        barriers.add(0)  # Add initial barrier at position 0\n\n        # Process the add-barrier queries to populate the barriers list\n        for query in queries:\n            if query[0] == 1:\n                it = query[1]\n                barriers.add(it)\n\n        holes = SortedList()  # Sorted list to maintain hole sizes\n        holes.add(float(\'inf\'))  # Initialize with an infinitely large hole\n        hole2start = {float(\'inf\'): barriers[-1]}\n\n        # Calculate initial hole sizes based on the barriers\n        for pos in range(len(barriers) - 1):\n            start = barriers[pos]\n            end = barriers[pos + 1]\n            size = end - start\n            if size:\n                pos = holes.bisect_left(size)\n                hole_size = holes[pos]\n                if hole2start[hole_size] > start:\n                    if hole_size > size:\n                        holes.add(size)\n                    hole2start[size] = start\n\n        barriers.add(float(\'inf\'))  # Add an infinite barrier at the end\n \n        result = []\n        # Process the queries in reverse order\n        for query in reversed(queries):\n            if query[0] == 1:  # If it\'s an add-barrier query\n                it = query[1]\n                pos = barriers.bisect_left(it)\n                left = barriers[pos - 1]\n                right = barriers[pos + 1]\n                size = right - left\n\n                hole_pos = holes.bisect_left(size)\n                if hole2start[holes[hole_pos]] > left:\n                    while hole_pos > 0 and hole2start[holes[hole_pos - 1]] > left:\n                        del hole2start[holes[hole_pos - 1]]\n                        del holes[hole_pos - 1]\n                        hole_pos -= 1\n\n                    hole2start[size] = left\n                    if holes[hole_pos] != size:\n                        holes.add(size)\n\n                barriers.remove(it)\n            else:  # If it\'s a check-hole query\n                _, start, size = query\n                hole_pos = holes.bisect_left(size)\n                hole = holes[hole_pos]\n                result.append(hole2start[hole] <= start - size)\n\n        result.reverse()  # Reverse the result to match the original query order\n\n        return result\n```
['Binary Search', 'Ordered Set', 'Python3']