C++ discretization + Segment Tree O(nlog(n)) time 29ms


  • 1
    Z
    class Solution {
        vector<int> vec;
        int getId(int x) {
            return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
        }
        int m;
        int seg[2005 * 4], lazy[2005 * 4];
        
        void build(int rt, int left, int right) {
            seg[rt] = 0, lazy[rt] = -1;
            if (left == right) return;
            int mid = (left + right) / 2;
            build(rt * 2, left, mid);
            build(rt * 2 + 1, mid + 1, right);
        }
        
        void add(int rt, int left, int right, int L, int R, int val) {
            if (L <= left && right <= R) {
                seg[rt] = lazy[rt] = val;
                return;
            }
            pushDown(rt, left, right);
            
            int mid = (left + right) / 2;
            
            if (L <= mid) add(rt * 2, left, mid, L, R, val);
            if (R > mid) add(rt * 2 + 1, mid + 1, right, L, R, val);
            
            seg[rt] = max(seg[rt * 2], seg[rt * 2 + 1]);
        }
        
        
        void pushDown(int rt, int left, int right) {
            // use lazy symbol to reduce the segment tree traverse, only update the son when needed
            if (lazy[rt] != -1) {
                seg[rt * 2] = lazy[rt * 2] = lazy[rt * 2 + 1] = seg[rt * 2 + 1] = lazy[rt];
                lazy[rt] = -1;
            }
        }
        
        int query(int rt, int left, int right, int L, int R) {
             if (L <= left && right <= R) {
                return seg[rt];
            }
            pushDown(rt, left, right);
            
            int mid = (left + right) / 2;
            
            int res = -1;
            if (L <= mid) res = max(res, query(rt * 2, left, mid, L, R));
            if (R > mid) res = max(res, query(rt * 2 + 1, mid + 1, right, L, R));
            
            return res;
        }
    public:
        vector<int> fallingSquares(vector<pair<int, int>>& positions) {
            int n = positions.size();
            
            for (int i = 0; i < n; i++) {
                vec.push_back(positions[i].first);
                vec.push_back(positions[i].first + positions[i].second - 1);
            }
            
            
            //discretization
            sort(vec.begin(), vec.end());
            vec.erase(unique(vec.begin(), vec.end()), vec.end());
            
            m = vec.size();
            
            //build tree
            build(1, 1, m);
            
            vector<int> res;
            int curMax = 0;
            
            //insert segment to tree and query
            for (int i = 0; i < n; i++) {
                
                //use discretization to reduce the size of segment tree
                int l = getId(positions[i].first);
                int r = getId(positions[i].first + positions[i].second - 1);
                
                
                // query the maxHeight from l to r
                int segMax = query(1, 1, m, l, r);
                
                int newHeight = segMax + positions[i].second;
                
                // add new height to segment tree from l to r
                add(1, 1, m, l, r, newHeight);
                    
                curMax = max(curMax, newHeight);
                
                res.push_back(curMax);
            }
            
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.