Using only ordered Map; Beats 100% C++ submissions
Intuition\n Describe your first thoughts on how to solve this problem. \nIf we have data of maximum available interval/gap before each blocks, then we can use b
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf we have data of maximum available interval/gap before each blocks, then we can use binary search to find the answer to the query of type 2.\n\nBut for query of type 1: We need to add new blocks and update all other blocks with **x** greater than the **current x**. Here we have to use data structure that keeps order. Vector or Map is ideal. But vector will have higher time complexity since insertion is always O(n), but for Map it is O(log n)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n#### For query of type 1: \ninsert the **key x** and **value: maximum available interval till x**. => **O(log n)**\nThen **update** the values of all the map nodes with **key greater than x** => worst case **O(n)**\n\n\n#### For query of type 2: \nfind the node with key equal to or greater than "x"; => Binary search on map => **O(log n)**\n\ncheck if key == x, then maximum interval available is value stored in the map with key = x\nelse maximum interval available = max(value stored in the map with key = x   and,  distance between x and the key in map just smaller than x) \n\nThen compare with the sz to check if we have available interval of size sz.\n# Complexity\n## Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n##### For query of type 1:\nworst case: O(n^2)\n##### For query of type 2:\nO(log n)\n## Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n): for storing Map\n# Code\n```\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        map<int,int> mp;\n        vector<bool> ans;\n        for(int i=0; i<queries.size(); i++){\n            if(queries[i][0] == 1){\n                int x = queries[i][1]; //blockage\n                \n                map<int,int>::iterator it = mp.lower_bound(x);\n                if(it == mp.begin()){\n                    mp.insert(make_pair(x, x));    \n                }else{\n                    mp.insert(make_pair(x, max(x- prev(it)->first, prev(it)->second)));\n                }\n                \n                //update max of all elements\n                it = mp.upper_bound(x);\n                \n                for(; it!=mp.end(); it++){\n                    int prev_max = it->second;\n                    it->second = max(prev(it)->second, it->first - prev(it)->first);\n                    if(it->second == prev_max) break;\n                }\n            } else{\n                int x = queries[i][1];\n                int sz = queries[i][2];\n                \n                map<int,int>::iterator it = mp.lower_bound(x);\n                if(it == mp.end() || it->first !=x){\n                    int m;\n                    if(it == mp.begin()){\n                        m = x;\n                    }else m = max(x-prev(it)->first, prev(it)->second);\n                    \n                    if(m>=sz) ans.push_back(true);\n                    else ans.push_back(false);\n                }else{\n                    if(it->second >= sz)  ans.push_back(true);\n                    else ans.push_back(false);\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
['Ordered Map', 'C++']