easiest solution of hardest problem on leetcode
Intuition/Approach\nHandling Query Type 1:\n\nWhen we encounter a query to add an obstacle at position x, we perform the following steps:\n- If there\'s an obst
# Intuition/Approach\n**Handling Query Type 1:**\n\nWhen we encounter a query to add an obstacle at position x, we perform the following steps:\n- If there\'s an obstacle to the left of x, we calculate the gap between x and this left obstacle and update the segment tree.\n- If there\'s an obstacle to the right of x, we calculate the gap between this right obstacle and x and update the segment tree.\n- We then insert x into our set of obstacles.\n\n**Handling Query Type 2:**\n\nWhen we encounter a query to check if a block of size sz can be placed within the range [0, x], we perform the following steps:\n- We query the segment tree for the maximum gap in the range [0, x].\n- If there is an obstacle to the left of x, we calculate the gap between x and this left obstacle and compare it with sz.\n- If the maximum gap found is greater than or equal to sz, then it is possible to place the block, and we return true. Otherwise, we return false.\n\n# Complexity\n- Time complexity:\n  O(n log(n)) where n is 150000\n\n- Space complexity:\n   O(4*n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution\n{\npublic:\n\n// -----segment tree(max) template starts here-------------\n\n    vector<long long> sgt;\n    int sz;\n\n    void init(int n)\n    {\n        sz = n;\n        sgt.assign(4 * n, 0);\n    }\n\n    void update(int v, int tl, int tr, int pos, int val)\n    {\n        if (tl == tr and tl == pos)\n        {\n            sgt[v] = val;\n            return;\n        }\n        int mid = (tl + tr) / 2;\n        if (pos <= mid)\n        {\n            update(2 * v, tl, mid, pos, val);\n        }\n        else\n        {\n            update(2 * v + 1, mid + 1, tr, pos, val);\n        }\n        sgt[v] = max(sgt[2 * v], sgt[2 * v + 1]);\n    }\n    void update(int pos, int val)\n    {\n        update(1, 0, sz - 1, pos, val);\n    }\n\n    long long query(int v, int tl, int tr, int l, int r)\n    {\n        if (l > tr or r < tl)\n            return 0;\n        if (tl >= l and tr <= r)\n        {\n            return sgt[v];\n        }\n        int mid = (tl + tr) / 2;\n        long long lc = query(2 * v, tl, mid, l, r);\n        long long rc = query(2 * v + 1, mid + 1, tr, l, r);\n        return max(lc, rc);\n    }\n    long long query(int l, int r)\n    {\n        return query(1, 0, sz - 1, l, r);\n    }\n\n\n//---------segment tree(max) template ends here-----------\n\n\n    vector<bool> getResults(vector<vector<int>> &queries)\n    {\n\n        int n = 15 * 10000 + 1;\n        init(n); // initializing sgt\n        set<int> st;\n        vector<bool> ans;\n   /* inserting 0 and 150000 into the set as it would not\n    affect the answer but will make implementaion easier */\n        st.insert(0);\n        st.insert(15 * 10000);\n        \n        for (auto it : queries)\n        {\n\n            if (it[0] == 1)\n            {\n                if (st.lower_bound(it[1]) != st.begin()) \n                {\n                    int lf = (*--st.lower_bound(it[1]));\n\n                    update(it[1], it[1] - lf);\n                }\n                if (st.upper_bound(it[1]) != st.end())\n                {\n                    int rt = (*st.upper_bound(it[1]));\n\n                    update(rt, rt - it[1]);\n                }\n                st.insert(it[1]);\n            }\n            else\n            {\n\n                int q = query(0, it[1]);\n\n                if (st.lower_bound(it[1]) != st.begin())\n                {\n                    int lf = (*--st.lower_bound(it[1]));\n\n                    q = max(q, it[1] - lf);\n                }\n\n                if (q >= it[2])\n                {\n                    ans.push_back(true);\n                }\n                else\n                    ans.push_back(false);\n            }\n        }\n\n        return ans;//please upvote\n    }\n};\n```\n\n\n
['C++']