C++||explanation||bsearch||722ms
Approach\n Describe your first thoughts on how to solve this problem. \n- Use an ordered hash map to maintain obstacles. \n  For each obstacle, it stores locati
# Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Use an ordered hash map to maintain obstacles. \n  For each obstacle, it stores location $$x$$ and the maximum segement length so far to the obstacle. A pair of adjacent obstacles forms a segment.\n  E.g. for obstacles at $$x=2, 8, 10, 20$$, \n  the hash map will be $$(2, 2), (8, 6), (10, 6), (20, 10)$$. A few clarifications:\n  - For obstacle $$x=10$$, the maximum segment length so far to it is $$6$$ (from $$max([2,8], [8,10])=6$$), so $$(10,6)$$ stored.\n  - For obstacle $$x=20$$, the maximum segment length so far to it is $$10$$ (from $$max([2,8], [8,10], [10,20])=10$$), so $$(20,10)$$ stored.\n- When adding a new obstacle, adjust and update above hash map.\n  From above example, add a new obstacle $$x=5$$, the hash map will become $$(2,2), \\bold{(5, 3)}, (8, \\bold{3}), (10, \\bold{3}), (20, 10)$$\n- When querying, use binary search to find the nearest and lower obstacle. And then compare the $$sz$$ with the stored maximum segment length data of that obstacle and the distance between new $$x$$ and that obstacle to check whether able to fit $$sz$$.\n  For example query $$x=12, sz=6$$, it binary-searches the obstacle $$x=10$$ first, get data $$(10, 6)$$. Due to $$sz <= 6$$, it means at least one segment before the obstacle able to fit it. Return true.\n  For example query $$x=18, sz=7$$, it binary-searches the obstacle $$x=10$$ first, get data $$(10,6)$$. Due to $$sz > 6$$ ($$sz$$ is not $$<= 6$$), there is NO segment before that obstacle able to fit it. Change to check the segment between that obstacle and the query. It\'s $$18-10=8$$ in length, and $$sz <= 8$$ so able to fit it. Return true.\n- The approach is very fast for query but slow in adding obstacle.\n\n\n# Complexity\n- Time complexity: $$O((N + M) \\cdot logN)$$, \n  N=the number of putting actions, M=the number of queries. More details following:\n  - Putting N obstacles: $$O(N \\cdot logN)$$ \n    Putting one obstacle to sorted map, which takes $$O(logN)$$, and then adjusting "value of max segment length between $$[0, \\space x \\space of \\space obstacle_{i}]$$" for each following obstacle$${i}$$ after the newly added obstacle, which takes $$O(N)$$ in worst case but near $$O(\\alpha)$$, $$\\alpha \u2248 1$$ in average. Why? In my opinion, it\'s obvious that the worst case happens only when the split was carried out on the maximum space for the following segments, and the opportunity is rare. So putting one obstacle takes $$O(logN)$$. \n    So N putting actions take $$O(N \\cdot logN)$$.\n    Please correct me if I am wrong.\n\n  - M queries: $$O(M \\cdot logN)$$\n    Each query uses binary search to address the nearest and lower obstacle, which takes $$O(logN)$$, and then does simple calculation to return.\n    So M queries take $$O(M \\cdot logN)$$\n\n\n- Space complexity: $$O(N)$$\n  N=the number of putting actions.\n  It uses hash map to maintain each obstacle in order of location with the maximum segement length so far to that obstacle.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\npublic:\n  vector<bool> getResults(vector<vector<int>>& queries) {\n    vector<bool> result;\n    std::map<int, int> obstacles;   // [x] => max segment between [0, x] so far\n    obstacles[0] = 0;               // put an obstacle in x=0 for conve.\n\n    for (const vector<int> &qry: queries) {\n      if (qry[0] == 1) {\n        // Phase 1: add the obstacle to hash map\n        auto [it, inserted] = obstacles.insert({qry[1], 0});\n        assert(inserted);     // must be true due to condition given.\n\n        // Phase 2: split the segment\n        //  prev obs.    new obs.\n        //  |            |                |\n        //  ^prev_it     ^new\n        //               ^it\n        //               ^last_x (qry[1])\n        auto prev_it = std::prev(it);\n        int last_max_space = it->second = max(prev_it->second, qry[1] - prev_it->first);\n        int last_x = it->first;\n\n        // Phase 3: adjust the following segments data.\n        for (++it; it != obstacles.end(); ++it) {\n          int d = max(last_max_space, it->first - last_x);\n          if (d == it->second) \n            break;\n          last_max_space = it->second = d;\n          last_x = it->first;\n        }\n      }\n      else {\n        // Find the nearest and lower obstacle\n        auto it = std::prev(obstacles.upper_bound(qry[1]));\n        // Compare with \n        //   the maximum segment length so far to the found obstacle\n        //   and the segment between the found obstacle and the query x\n        result.push_back(qry[2] <= it->second || qry[2] <= qry[1] - it->first);\n      }\n    }\n\n    return result;\n  }\n};\n```
['Hash Table', 'Binary Search', 'C++']