Simple and Fast c++ using interval tree, beat 99.99%
// map  means current height in interval\n// update by each position\n\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<pair<int, int>>& positi
// map <start, {end, height}> means current height in interval\n// update by each position\n```\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n        map<int, pair<int,int>> m;\n        vector<int> res;\n        int maxM = 0;\n        for (const auto& p:positions)\n        {\n            int left = p.first, right = left+p.second;\n            int curM = 0;\n            auto it = m.upper_bound(left);\n            if (it != m.begin())\n            {\n                --it;\n                if (it->second.first <= left)  ++it;\n            }\n            while (it != m.end() and it->first < right)\n            {\n                curM = max(curM, it->second.second); \n                if (it->second.first > right)\n                {\n                    m[right] = it->second;\n                }\n                if (it->first < left){\n                    it->second = {left, it->second.second};\n                    it++;\n                }\n                else m.erase(it++);\n            }\n            m[left] = {right, curM+p.second};\n            maxM = max(maxM, curM+p.second);\n            res.push_back(maxM);\n        }\n        return res;\n    }\n};\n```
[]