Ordered map for storing obstacles
Intuition\n Describe your first thoughts on how to solve this problem. \nRepresent the obstacles using a map, where a key is the position of an obstacle and the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nRepresent the obstacles using a map, where a key is the position of an obstacle and the value is the size of the largest box, which fits between position `0` and this obstacle.\n\nProcessing querys of type 2 is then fast and easy, as we can use a binary search to find the relevant obstacle and use the stored value to check, if the box fits.\n\nThe difficulty is updating the map, when new obstacles are inserted, as we potentially need to ensure that the stored sizes remain correct.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nInitially we use a dummy obstacle at position zero to make it easier to compute the differences between obstacles.\nWhen a new obstacle is inserted, its value has to be computed. Potentially, this new insertion also invalidates the values of the subsequent obstacles, as the insertion may have split the largest gap between 0 and the respective obstacle.\nTherefore, we iterate through the subsequent obstacles, until an obstacles is reached whose value does not need to be updated, becuase its previous value did not depend on the gap the newly added obstacle was inserted into. From this position on, the subsequent obstacles do not need to be updated either, which means that we can terminate the updating early.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nWorst case: $$O(n^2)$$. In the worst case, every iteration of the outer loop updates all values in the map.\nAverage case: Probably $$O(n\\cdot\\log n)$$. Insertion and binary search require logarithmic time. On average, the updating should require a small number of steps. However, I have no idea how to estimate this in the average case.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        vector<bool> results;\n        \n        // create map with obstacles. initialize with dummy obstacles at 0\n        map<unsigned short, unsigned short> obstacles{{0, 0}};\n        for (const vector<int> &query : queries)\n        {\n            if (query[0] == 1) // Type 1 = add obstacle\n            {\n                // insert obstacle and retrieve inserted position\n                auto insertion_result = obstacles.insert({static_cast<unsigned short>(query[1]), 0});\n\n                for (auto it = get<0>(insertion_result), previous = prev(it); it != obstacles.end(); ++it, ++previous)\n                {\n                    // Update values to reflect new distances\n                    auto new_value = max(previous->second, static_cast<unsigned short>(it->first - previous->first));\n                    // Stop inserting, if we reach a position, where the values are no longer updated\n                    if (it->second == new_value)\n                    {\n                        break;\n                    }\n                    it->second = new_value;\n                }\n            }\n            else // Type 2 = check if box fits\n            {\n                // Get iterator to last obstacle within [0, x]\n                auto it = --obstacles.lower_bound(static_cast<unsigned short>(query[1]));\n\n                // Compute the last gap from last obstacle to x\n                unsigned short last_gap = static_cast<unsigned short>(query[1] - (it)->first);\n\n                // check if box fits and store answer\n                results.push_back(max(it->second, last_gap) >= static_cast<unsigned short>(query[2]));\n            }\n        }\n        return results;\n    }\n};\n```
['C++']