Leetcode 2297 Solution

This article provides solution to leetcode question 2297 (amount-of-new-area-painted-each-day)
Categories:
Tags:
Access this page by simply typing in "lcs 2297" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/amount-of-new-area-painted-each-day

Solution

class SegmentTree:
    def __init__(self, n, start, end):
        self.nodes = [0] * (4 * n + 1)
        self.start = start
        self.end = end

    def update(self, i, l, r, start=None, end=None):
        if start is None and end is None:
            start = self.start
            end = self.end

        if l > end or r < start:
            return 0

        if start == end:
            if self.nodes[i] == 0:
                self.nodes[i] = 1
                return 1
            else:
                return 0

        if end - start + 1 == self.nodes[i]:
            return 0

        mid = (start + end) // 2
        lcnt = self.update(2 * i + 1, l, r, start, mid)
        rcnt = self.update(2 * i + 2, l, r, mid + 1, end)
        self.nodes[i] += lcnt + rcnt
        return lcnt + rcnt

class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        st = SegmentTree(50001, 0, 49999)
        ans = []
        for l, r in paint:
            ans.append(st.update(0, l, r - 1))
        return ans