2 Solution | Set, Segment Tree
Solution-1 (Set) -- (TLE -- 737 / 742 test cases passed -- 99.32%)\n+ Using set to store the blocks in order.\n+ For each query:\n\t1) If set is empty, it means
# Solution-1 (Set) -- (TLE -- 737 / 742 test cases passed -- 99.32%)\n+ Using set to store the blocks in order.\n+ For each query:\n\t1) If set is empty, it means no blocks are present -- Hence return true (we can place the block).\n\t2) If set is not empty, it means some blocks are present -- Traverse all blocks and Identify the maxBlock that we can place. Return true if we can place the block, false otherwise.\n# Code:\n```\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) \n    {\n        set<int> s;\n        vector<bool> ans;\n        \n        for ( auto query : queries ) \n        {\n            int type = query[0];\n            \n            if ( type == 1 )\n            {\n                int x = query[1];\n                s.insert(x);\n            } \n            else // type == 2\n            {\n                int x = query[1], blockSize = query[2];\n                \n                if ( blockSize > x )\n                    ans.push_back(false);\n                else\n                {\n                    if ( s.size() == 0 )\n                        ans.push_back(true);\n                    else {\n                        int maxBlock = *(s.begin());\n                        auto it = s.begin();\n                        auto nextIt = std::next(it);\n                        \n                        while ( nextIt != s.end() )\n                        {\n                            if ( x < *nextIt ) {\n                                maxBlock = max(maxBlock, x - *it);\n                                break;\n                            }\n                            maxBlock = max(maxBlock, *nextIt - *it);\n                            it++;\n                            nextIt++;\n                        }\n                        maxBlock = max(maxBlock, x - *it);\n                        \n                        if ( maxBlock >= blockSize )\n                            ans.push_back(true);\n                        else\n                            ans.push_back(false);\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n};\n```\n\n# Solution-2: Segment Tree\n# Code\n```\nclass SegTree\n{\npublic:\n\tSegTree(int _n)\n\t{\n\t\tn = _n;\n\t\ttree.resize(n * 4, 0);\n\t}\n\n\tint GetMax(int x) const\n\t{\n\t\treturn GetRangeValueInternal(0, x, 1, 0, n - 1);\n\t}\n\n\tvoid UpdateValue(int index, int newValue)\n\t{\n\t\tUpdateValueInternal(index, newValue, 1, 0, n - 1);\n\t}\n\nprivate:\n\tint GetRangeValueInternal(int left, int right, int nodeIndex, int nodeRangeLeftIndex, int nodeRangeRightIndex) const\n\t{\n\t\tif (left > right)\n\t\t\treturn 0;\n\n\t\tif (left == nodeRangeLeftIndex && right == nodeRangeRightIndex)\n\t\t\treturn tree[nodeIndex];\n\n\t\tint rangeMid = (nodeRangeLeftIndex + nodeRangeRightIndex) / 2;\n\t\tint leftV = GetRangeValueInternal(left, min(right, rangeMid), nodeIndex * 2, nodeRangeLeftIndex, rangeMid);\n\t\tint rightV = GetRangeValueInternal(max(left, rangeMid + 1), right, nodeIndex * 2 + 1, rangeMid + 1, nodeRangeRightIndex);\n\t\treturn max(leftV, rightV);\n\t}\n\n\tvoid UpdateValueInternal(int index, int newValue, int nodeIndex, int nodeRangeLeftIndex, int nodeRangeRightIndex)\n\t{\n\t\tif (nodeRangeLeftIndex == nodeRangeRightIndex)\n\t\t{\n\t\t\ttree[nodeIndex] = newValue;\n\t\t\treturn;\n\t\t}\n\n\t\tint mid = (nodeRangeLeftIndex + nodeRangeRightIndex) / 2;\n\t\tint leftChild = nodeIndex * 2;\n\t\tint rightChild = leftChild + 1;\n\t\tif (index <= mid)\n\t\t{\n\t\t\tUpdateValueInternal(index, newValue, leftChild, nodeRangeLeftIndex, mid);\n\t\t}\n\t\telse\n\t\t{\n\t\t\tUpdateValueInternal(index, newValue, rightChild, mid + 1, nodeRangeRightIndex);\n\t\t}\n\t\ttree[nodeIndex] = max(tree[leftChild], tree[rightChild]);\n\t}\n\n\tint n;\n\tvector<int> tree;\n};\n\nconstexpr int MaxX = 50001;\n\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries)\n\t{\n\t\tSegTree seg(MaxX);\n\t\tset<int> obs;\n        // Consider the max x and 0 as existing obstacles\n\t\tobs.insert(0);\n\t\tobs.insert(MaxX);\n\n\t\tvector<bool> ans;\n\t\tfor (auto& q : queries)\n\t\t{\n\t\t\tint x = q[1];\n\t\t\tif (q[0] == 1)\n\t\t\t{\n                // x will never already exist in obs, so the returned itr will\n                // always be r of the existing gap and l will be the prevous one\n\t\t\t\tauto itr = obs.upper_bound(x);\n\t\t\t\tint r = *itr;\n\t\t\t\tint l = *(--itr);\n\t\t\t\tobs.insert(x);\n\t\t\t\tseg.UpdateValue(x, x - l);\n\t\t\t\tseg.UpdateValue(r, r - x);\n\t\t\t}\n\t\t\telse\n\t\t\t{\n\t\t\t\tint sz = q[2];\n                // First check the segment tree for the max gap before x\n\t\t\t\tbool isValid = seg.GetMax(x) >= sz;\n                // But if we don\'t find one,\n                // then we should also check the gap which x falls into\n                // as there is the space from [l,x] which is not accounted for\n                // in the segment tree if no obstable exists at x\n\t\t\t\tif (!isValid)\n\t\t\t\t{\n\t\t\t\t\tauto itr = obs.lower_bound(x);\n\t\t\t\t\tif (*itr != x)\n\t\t\t\t\t{\n                        int l = *(--itr);\n\t\t\t\t\t\tisValid = (x - l) >= sz;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tans.push_back(isValid);\n\t\t\t}\n\t\t}\n\n\t\treturn ans;\n\t}\n};\n```
['Tree', 'C', 'Ordered Set']