# On an infinite number line (x-axis), we drop given squares in the order they are given.
#
# The i-th square dropped (positions[i] = (left, side_length)) is a square with the left-most point being positions[
# i][0] and sidelength positions[i][1].
#
# The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently
#  landed squares. We wait for each square to stick before dropping the next.
#
# The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they
# touch (either the number line or another square). Squares dropped adjacent to each other will not stick together
# prematurely.
#
#
# Return a list ans of heights. Each height ans[i] represents the current highest height of any square we have
# dropped, after dropping squares represented by positions[0], positions[1], ..., positions[i].
#
# Example 1:
# Input: [[1, 2], [2, 3], [6, 1]]
# Output: [2, 5, 5]
# Explanation:
#
# After the first drop of positions[0] = [1, 2]:
# _aa
# _aa
# -------
# The maximum height of any square is 2.
#
#
# After the second drop of positions[1] = [2, 3]:
# __aaa
# __aaa
# __aaa
# _aa__
# _aa__
# --------------
# The maximum height of any square is 5.
# The larger square stays on top of the smaller square despite where its center
# of gravity is, because squares are infinitely sticky on their bottom edge.
#
#
# After the third drop of positions[1] = [6, 1]:
# __aaa
# __aaa
# __aaa
# _aa
# _aa___a
# --------------
# The maximum height of any square is still 5.
#
# Thus, we return an answer of [2, 5, 5].
#
#
# Example 2:
# Input: [[100, 100], [200, 100]]
# Output: [100, 100]
# Explanation: Adjacent squares don't get stuck prematurely - only their bottom edge can stick to surfaces.
# Note:
#
# 1 <= positions.length <= 1000.
# 1 <= positions[i][0] <= 10^8.
# 1 <= positions[i][1] <= 10^6.
import bisect


class Interval:
    def __init__(self, s, e, h):
        self.start = s
        self.end = e
        self.height = h

    def __repr__(self):
        return "[{}, {}, {}]".format(self.start, self.end, self.height)


class Solution(object):
    def fallingSquares_wrong(self, positions):
        """
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        res = []

        def start_upper_bound(pos, target):
            l, r = 0, len(pos) - 1
            while l <= r:
                mid = l + (r - l) / 2
                if pos[mid].start < target.end:
                    l = mid + 1
                else:
                    r = mid - 1

            return l

        def end_lower_bound(pos, target):
            l, r = 0, len(pos) - 1
            while l <= r:
                mid = l + (r - l) / 2
                if pos[mid].end < target.start:
                    l = mid + 1
                else:
                    r = mid - 1

            return l

        squares = []

        for p in positions:
            target = Interval(p[0], p[0] + p[1], p[1])
            if not squares:
                squares.append(target)
                res.append(target.height)
                continue
            start_upper, end_lower = start_upper_bound(squares, target), end_lower_bound(squares, target)

            if start_upper < len(squares) and squares[start_upper].start < target.end:
                start_upper += 1
            if 0 < end_lower < len(squares) and squares[end_lower].end > target.start:
                end_lower -= 1

            insert, h, i = -1, 0, end_lower
            while i < start_upper:
                if insert == -1 and (target.start < squares[i].start or \
                                     (target.start == squares[i].start and target.end < squares[i].end)):
                    insert = i
                if target.start < squares[i].end:
                    h = max(h, squares[i].height + target.height)

                i += 1

            if h == 0:
                h = target.height
            res.append(max(h, max(res)))

            insert = insert if insert > -1 else start_upper
            squares.insert(insert, Interval(target.start, target.end, h))

        return res

    # brute force
    def fallingSquares(self, positions):
        """
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        res, length = [], len(positions)
        heights = [0] * length

        for i, p in enumerate(positions):
            left, right, height = p[0], p[0] + p[1], p[1]
            heights[i] += height

            for j in xrange(i + 1, length):
                l, r, h = positions[j][0], positions[j][1] + positions[j][0], positions[j][1]
                if l < right and r > left:
                    # bugfixed,
                    heights[j] = max(heights[j], heights[i])

        cur = 0
        for h in heights:
            cur = max(cur, h)
            res.append(cur)

        return res


class Solution2(object):
    def fallingSquares2(self, positions):
        """
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        height, pos, res, max_h = [0], [0], [], 0
        for left, side in positions:
            i = bisect.bisect_right(pos, left)
            j = bisect.bisect_left(pos, left + side)
            print i, j

            high = max(height[i - 1:j] or [0]) + side
            pos[i:j] = [left, left + side]
            print pos
            height[i:j] = [high, height[j - 1]]
            print height
            max_h = max(max_h, high)
            res.append(max_h)

        return res



if __name__ == '__main__':
    print Solution2().fallingSquares2([[1, 2], [2, 3], [2, 4], [6, 1]])
    print Solution().fallingSquares([[100, 100], [200, 100]])
    print Solution().fallingSquares([[6, 1], [9, 2], [2, 4]])
    print Solution().fallingSquares([[9, 6], [2, 2], [2, 6]])
    print Solution().fallingSquares([[4, 1], [6, 9], [6, 8], [1, 9], [9, 8]])
