Submission #851633

#	Time	Username	Problem	Language	Result	Execution time	Memory
851633		tester777	Street Lamps (APIO19_street_lamps)	Cpython 3	0 / 100	1731 ms	4024 KiB

street_lamps

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)

    def update(self, node, start, end, idx):
        if start == end:
            self.tree[node] ^= 1  # Toggle the lamp state
        else:
            mid = (start + end) // 2
            if start <= idx <= mid:
                self.update(2 * node + 1, start, mid, idx)
            else:
                self.update(2 * node + 2, mid + 1, end, idx)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, node, start, end, left, right):
        if left > end or right < start:
            return 0
        if left <= start and right >= end:
            return self.tree[node]
        mid = (start + end) // 2
        left_sum = self.query(2 * node + 1, start, mid, left, right)
        right_sum = self.query(2 * node + 2, mid + 1, end, left, right)
        return left_sum + right_sum

n, q = map(int, input().split())
lamp_states = list(map(int, input().strip()))

# Initialize the segment tree
segment_tree = SegmentTree(n)

# Process events
for _ in range(q):
    event = input().split()
    if event[0] == "toggle":
        i = int(event[1]) - 1
        segment_tree.update(0, 0, n - 1, i)
    else:  # Event is a query
        a, b = map(int, event[1:])
        time = segment_tree.query(0, 0, n - 1, a - 1, b - 2)
        print(time)

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20