Submission details
Task:Dynamic Range Minimum Queries
Sender:aalto26dh_007
Submission time:2026-09-21 23:06:10 +0300
Language:C++ (C++23)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.10 sdetails

Code

#include <iostream>
#include <vector>
#include <string>
#include <format>
#include <algorithm>
#include <climits>


int main (int argc, char **argv) {

    int n, q;
    std::cin >> n >> q;

    std::vector<int> numbers(n, 0);
    for (int i=0; i<n; i++) {
        std::cin >> numbers[i];
    }

    //std::cout << std::format("{}", numbers) << std::endl;

    std::vector<int> tree(2 * n, 0);
    for (int i=0; i<n; i++) {
        tree.at(n + i) = numbers.at(n);
    }
    for (int i=n-1; i>0; i--) {
        tree.at(i) = std::min(tree.at(2*i), tree.at(2*i+1));
    }

    std::string result;
    for (int i=0; i<q; i++) {
        int t, a, b;
        std::cin >> t >> a >> b;
        
        if (t == 1) {
            int pos = (a - 1) + n;
            tree.at(pos) = b;

            pos = pos / 2;
            while (pos > 0) {
                tree.at(pos) = std::min(tree.at(2*pos), tree.at(2*pos+1));
                pos = pos / 2;
            }
        } else {
            int l = (a - 1) + n;
            int r = b + n;
            int minimum = INT_MAX;

            while (l < r) {
                if (l % 2 == 1) {
                    minimum = std::min(minimum, tree.at(l));
                    l++;
                }
                if (r % 2 == 1) {
                    r--;
                    minimum = std::min(minimum, tree.at(r));
                }
                l = l / 2;
                r = r / 2;
            }

            result += std::to_string(minimum) + '\n';
        }
    }

    std::cout << result << std::endl;


    return 0;
}

Test details

Test 1

Verdict:

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
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 8) >= this->size() (which is 8)

Test 2

Verdict:

input
200000 200000
398739055 65343131 699208332 3...

correct output
28609
129890
20378
20378
311522
...

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 200000) >= this->size() (which is 200000)