set + segment Tree
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nuse set of pairs to mai
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nuse set of pairs to maintain the empty spaces available. first element of pair will denote the position from where empty space begin and second element denotes the size of that empty space. inially we have whole number line available thats why i pushed(0, L). L denotes last point on number line possible.\n\nthan i used segment tree because we need to update the spaces available if a new obstacle come and also find the maximum space avail between 0 and x. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\nprivate:\n    typedef pair<int, int> pi;\n    int L = 5e4 + 10;\n\n    vector<int> arr, t;\n\n    void update(int index, int l, int r, int pos, int val) {\n        if(pos < l || pos > r) return;\n        if(l == r) {\n            t[index] = val;\n            arr[pos] = val;\n            return;\n        }\n\n        int mid = (l + r) / 2;\n\n        if(pos <= mid) {\n            update(2 * index, l, mid, pos, val);\n        } else {\n            update(2 * index + 1, mid + 1, r, pos, val);\n        }\n\n        t[index] = max(t[2 * index], t[2 * index + 1]);\n    }\n\n    int query(int index, int l, int r, int lq, int rq) {\n        if (lq > r || l > rq) {\n            return 0;\n        }\n        if (lq <= l && r <= rq) {\n            return t[index];\n        }\n        \n        int mid = (l + r) / 2;\n        \n        return max(query(2 * index, l, mid, lq, rq),query(2 * index + 1, mid + 1, r, lq, rq));\n    }\npublic: \n    vector<bool> getResults(vector<vector<int>>& queries) {\n        arr.resize(L, 0), t.resize(4*L, 0);\n\n        vector<bool> res;\n        set<pair<int, int>> obstacleRange;\n        obstacleRange.insert({0, L});\n\n        for(auto &q: queries) {\n            int type = q[0], pos = q[1];\n\n            if(type == 1) {\n                pair<int, int> currRange;\n                currRange.first = pos;\n\n                auto it = obstacleRange.lower_bound({pos, -1e9});\n                if(it != obstacleRange.end()) {\n                    currRange.second = it -> first - pos;\n                } else {\n                    currRange.second = L - pos;\n                }\n                it--;\n\n                pair<int, int> prevRange = *it;\n                prevRange.second = pos - prevRange.first;\n                obstacleRange.erase(it);\n                obstacleRange.insert(prevRange);\n                obstacleRange.insert(currRange);\n\n                update(1, 0, L-1, prevRange.first, prevRange.second);\n                update(1, 0, L-1, currRange.first, currRange.second);\n            } else {\n                int sz = q[2];\n\n                auto it = obstacleRange.lower_bound({pos, -1e9});\n                it--;\n                int maxSpacePossible = pos - (it -> first);\n\n                if(it != obstacleRange.begin()) {\n                    it--;\n                    pair<int, int> prevRange = *it;\n                    int lq = 0, rq = it -> first;\n                    maxSpacePossible = max(maxSpacePossible, query(1, 0, L-1, lq, rq));\n                }\n\n                if(maxSpacePossible >= sz) {\n                    res.push_back(true);\n                } else {\n                    res.push_back(false);\n                }\n            }\n        }\n\n        return res;\n    }\n};\n```
['Binary Search', 'Segment Tree', 'Ordered Set', 'C++']