oj.uz

Submission #851633

# Submission time Handle Problem Language Result Execution time Memory
851633 2023-09-20T09:50:34 Z tester777 Street Lamps (APIO19_street_lamps) Python 3
0 / 100
 1731 ms 4024 KB 
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1731 ms 4024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 3136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -