Submission #71508998

---

Source Code Expand

def main():
    MAX = 10**5  # Max size of array
    tree = [0] * (4 * MAX)  # Segment tree
    lazy = [0] * (4 * MAX)  # Lazy array

    # Function to update the segment tree
    def updateRange(node, start, end, l, r, val):
        # If lazy[node] is non-zero, then there are some
        # pending updates. So we need to make sure the node is
        # updated
        if lazy[node] != 0:
            # Updating the node
            tree[node] = (end - start + 1) * lazy[node]

            # Passing the update information to its children
            if start != end:
                lazy[node * 2] = lazy[node]
                lazy[node * 2 + 1] = lazy[node]

            # Resetting the lazy value for the current node
            lazy[node] = 0

        # Out of range
        if start > end or start > r or end < l:
            return

        # Current segment is fully in range
        if start >= l and end <= r:
            # Update the node
            tree[node] = (end - start + 1) * val

            # Pass the update information to its children
            if start != end:
                lazy[node * 2] = val
                lazy[node * 2 + 1] = val
            return

        # If not completely in range but overlaps, recur for children
        mid = (start + end) // 2
        updateRange(node * 2, start, mid, l, r, val)
        updateRange(node * 2 + 1, mid + 1, end, l, r, val)

        # Use the result of children calls to update this node
        tree[node] = tree[node * 2] + tree[node * 2 + 1]

    # Function to calculate the sum on a given range
    def queryRange(node, start, end, l, r):
        # Out of range
        if start > end or start > r or end < l:
            return 0

        # If there are pending updates
        if lazy[node] != 0:
            # Updating the node
            tree[node] = (end - start + 1) * lazy[node]

            # Passing the update information to its children
            if start != end:
                lazy[node * 2] = lazy[node]
                lazy[node * 2 + 1] = lazy[node]

            # Resetting the lazy value for the current node
            lazy[node] = 0

        # At this point, we are sure that pending lazy updates
        # are done for the current node. So we can return the value
        if start >= l and end <= r:
            return tree[node]

        # If not completely in range but overlaps, recur for children
        mid = (start + end) // 2
        p1 = queryRange(node * 2, start, mid, l, r)
        p2 = queryRange(node * 2 + 1, mid + 1, end, l, r)

        # Use the result of children calls to update this node
        return p1 + p2
    N, Q = map(int, input().split())
    queries = [list(map(int, input().split())) for _ in range(Q)]

    for l, r in queries:
        updateRange(1, 0, MAX - 1, l, r, 1)
        blacks = queryRange(1, 0, N-1, 0, N-1)
        print(N - blacks)

    
main()

Submission Info

Judge Result