CSES - Aalto Competitive Programming 2024 - wk4 - Homework - Results
Submission details
Task:Dynamic Range Minimum Queries
Sender:Mojojijo
Submission time:2024-09-24 22:04:08 +0300
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2--details

Code

def dyn_range_mn_queries(n, arr, barr):
    tree = [0] * (4 * n)
    lazy = [0] * (4 * n)

    def build(node, start, end):

        if start == end:
            tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            build(2 * node + 1, start, mid)  
            build(2 * node + 2, mid + 1, end)  
            tree[node] = min(tree[2 * node + 1], tree[2 * node + 2])

    def update_range(node, start, end, l, r, val):

        if lazy[node] != 0:
            tree[node] += lazy[node]
            if start != end:  
                lazy[2 * node + 1] += lazy[node]
                lazy[2 * node + 2] += lazy[node]
            lazy[node] = 0

        if start > end or start > r or end < l:
            return

        if start >= l and end <= r:
            tree[node] += val
            if start != end:  
                lazy[2 * node + 1] += val
                lazy[2 * node + 2] += val
            return

        mid = (start + end) // 2
        update_range(2 * node + 1, start, mid, l, r, val)
        update_range(2 * node + 2, mid + 1, end, l, r, val)
        tree[node] = min(tree[2 * node + 1], tree[2 * node + 2])

    def query_range(node, start, end, l, r):

        if lazy[node] != 0:
            tree[node] += lazy[node]
            if start != end:
                lazy[2 * node + 1] += lazy[node]
                lazy[2 * node + 2] += lazy[node]
            lazy[node] = 0

        if start > end or start > r or end < l:
            return float('inf')

        if start >= l and end <= r:
            return tree[node]

        mid = (start + end) // 2
        left_min = query_range(2 * node + 1, start, mid, l, r)
        right_min = query_range(2 * node + 2, mid + 1, end, l, r)
        return min(left_min, right_min)

    build(0, 0, n - 1)

    for query in barr:
        if query[0] == 1:

            _, k, u = query
            update_range(0, 0, n - 1, k - 1, k - 1, u - arr[k - 1])  
            arr[k - 1] = u
        else:
            _, a, b = query
            result = query_range(0, 0, n - 1, a - 1, b - 1)
            print(result)


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

barr = []
for _ in range(q):
    query = list(map(int, input().split()))
    barr.append(query)

dyn_range_mn_queries(n, arr, barr)


# Input:
# 8 4
# 3 2 4 5 1 1 5 3
# 2 1 4
# 2 5 6
# 1 2 3
# 2 1 4
# Output:
# 2
# 1
# 3

Test details

Test 1

Verdict: ACCEPTED

input
8 80
7 6 4 6 2 9 4 8
2 1 1
2 1 2
2 1 3
...

correct output
7
6
4
4
2
...

user output
7
6
4
4
2
...
Truncated

Test 2

Verdict:

input
200000 200000
398739055 65343131 699208332 3...

correct output
28609
129890
20378
20378
311522
...

user output
(empty)