C++ O(nlogn)
Similar to skyline concept, going from left to right the path is decomposed to consecutive segments, and each segment has a height. Each time we drop a new squa
Similar to skyline concept, going from left to right the path is decomposed to consecutive segments, and each segment has a height. Each time we drop a new square, then update the level map by erasing & creating some new segments with possibly new height. There are at most 2n segments that are created / removed throughout the process, and the time complexity for each add/remove operation is O(log(n)).\n\n```\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<pair<int, int>>& p) {\n        map<pair<int,int>, int> mp;\n        mp[{0,1000000000}] = 0;\n        vector<int> ans;\n        int mx = 0;\n        for (auto &v:p) {\n            vector<vector<int>> toAdd;\n            cout << endl;\n            int len = v.second, a = v.first, b =v.first + v.second, h = 0;\n            auto it = mp.upper_bound({a,a});\n            if (it != mp.begin() && (--it)->first.second <= a) ++it;\n            while (it != mp.end() && it->first.first <b) {\n                if (a > it->first.first) toAdd.push_back({it->first.first,a,it->second});\n                if (b < it->first.second) toAdd.push_back({b,it->first.second,it->second});\n                h = max(h, it->second);\n                it = mp.erase(it);\n            }\n            mp[{a,b}] = h + len;\n            for (auto &t:toAdd) mp[{t[0],t[1]}] = t[2];\n            mx = max(mx, h + len);\n            ans.push_back(mx);\n        }\n        \n        return ans;\n    }\n};\n```
[]