[C++][Explained] No fancy structures!! A straightforward solution using Set & Map beats 100%
Intuition\nMy idea is to find a way to keep all space of fixed size and their corresponding start position.\nThen, for any type2 query, we just need to check sp
# Intuition\nMy idea is to find a way to keep all space of fixed size and their corresponding **start position**.\nThen, for any type2 query, we just need to check spaces of the size greater than the request and check if the **start position** + **request size** exceeds the boundary, and  we may consider using an `OrderedMap: space -> start positions` to keep these spaces\n\n### How do we keep these start positions?\nWe may simpley keep them in UnorderedSet, for that we need to break a space into pieces on coming type1 queries. UnorderedSet performs inserect/delete operations in O(n) time.\nHowever, the type2 queries only set constraints to the right boundary. We may keep the start position of spaces in order, and then, for all spaces with the same size, we only need to check if the first one meets the request instead of looping through them all.\nAs a trade off, I finally decided to keep **start posttions** in a OrderedSet\n\n### How to update spaces when type1 query is coming?\n\n`0` ---- `pos_prev` ----- `pos_this` ----- `pos_next` ---- `maxi_dist`\n<table>\n  <tr>\n    <td></td>\n    <td>Start position</td>\n    <td>Size</td>\n  </tr>\n  <tr>\n    <td>Origin space</td>\n    <td>pos_prev</td>\n    <td>pos_next - pos_prev</td>\n  </tr>\n  <tr>\n    <td>New space (left)</td>\n    <td>pos_prev</td>\n    <td>pos - pos_prev</td>\n  </tr>\n  <tr>\n    <td>New space (right)</td>\n    <td>pos</td>\n    <td>pos_next - pos</td>\n  </tr>\n</table>\n\nAccording the table above, we may keep existing obstacles in a OrderedSet, and find `pos_prev`, `pos_next` in $O(logn)$ time, and then update spaces by a few OrderedMap inserection and delections .\n\n# Complexity\n- Time complexity:\n    Let `n` be the number of queries\n    Let `m` be the maximal distance\n    - Total: $O(n*(log(n)+\\sqrt{m}))$, we perform n queries, and for each query we do either of following\n        - breakSpaces: $O(logn)$\n        - ~findSpace: $O(n)$ In worse case we need to check all spaces~\n        - findSpace: $O(\\sqrt{m})$, for the worse case, we loop through spaces of difference size, and we can split our initial spzces into at most `x` spaces by $(1+2+....+x) = m$\n            $(1+2+...+x) \\le m$\n            $=> \\frac{(1+x)x}{2} \\le m$\n            $=> x^2 + x + \\frac{1}{4} \\le m + \\frac{1}{4}$\n            $=> (x+\\frac{1}{2})^2 \\le m + \\frac{1}{4}$\n            $=> (x+\\frac{1}{2}) \\le \\sqrt{m + \\frac{1}{4}}$\n\n- Space complexity:\n    - Total: $O(n)$\n        - ans: $O(n)$\n        - obstacles: $O(n)$, we can put at most `n` obstacle\n        - spaces $O(n)$, `n` obstackes from at most `n+1` space \n\n# Code\n```\nclass Solution {\n\n    void breakSpaces(int pos){\n        // break spaces\n        auto it = obstacles.upper_bound(pos);\n        int pos_next = *it;\n        int pos_prev = *prev(it);\n        // remove original space\n        int orig_size = pos_next - pos_prev;\n        spaces[orig_size].erase(pos_prev);\n        if(spaces[orig_size].size() == 0){ spaces.erase(orig_size); }\n        // add new space\n        spaces[pos - pos_prev].insert(pos_prev);\n        spaces[pos_next - pos].insert(pos);\n    }\n    \n    bool findSpace(int maxi_dist, int block_size){\n        auto it = spaces.lower_bound(block_size);\n        while(it != spaces.end()){\n            //for(int start_pos: it->second){\n            //    if(start_pos+block_size <= maxi_dist){\n            //        return true;\n            //    }\n            // }\n            // The start positions were sorted in order.\n            // Thus we only need to check the first one.\n            set<int> & start_positions = it->second;\n            int first_pos = *start_positions.begin();\n            if(first_pos + block_size <= maxi_dist){\n                return true;\n            }\n            advance(it, 1);\n        }\n        return false;\n    }\n\n    vector<bool> ans;\n    set<int> obstacles;        // To keep obstacle coordinate in order\n    map<int, set<int>> spaces; // keep group empty spaces in order. spaces: space_size -> start index\n        \npublic:\n    vector<bool> getResults(const vector<vector<int>>& queries) {\n        int const nquery = queries.size();\n        ans.reserve(nquery);\n        int maxi_dist = min(5*10e4, 3.0*nquery);\n        obstacles.insert(0);         // dummy obstacle\n        obstacles.insert(maxi_dist); // dummy obstacle\n        spaces[maxi_dist].insert(0); // initialize space\n\n        for(auto const & query: queries){\n            int op = query[0];\n            // op1: set obstacle\n            if(op == 1){\n                breakSpaces(query[1]);\n                obstacles.insert(query[1]);\n            }\n            // op2: put blocks\n            else{\n                ans.push_back(findSpace(query[1], query[2]));\n            }\n        }        \n        \n        return ans;\n    }\n};\n```
['Binary Search', 'Ordered Map', 'Ordered Set', 'C++']