Task: | Dynamic Range Minimum Queries |
Sender: | Farah |
Submission time: | 2024-09-24 10:20:21 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.12 s | details |
Code
#include <iostream> #include <vector> #include <algorithm> #include <climits> // Include this for INT_MAX using namespace std; class SegmentTree { public: int n; vector<int> tree; // Constructor to initialize the segment tree SegmentTree(const vector<int>& data) { n = data.size(); tree.resize(2 * n); build(data); } // Build the segment tree from the input data void build(const vector<int>& data) { // Insert leaf nodes in the tree for (int i = 0; i < n; ++i) { tree[n + i] = data[i]; } // Build the tree by calculating parents for (int i = n - 1; i > 0; --i) { tree[i] = min(tree[2 * i], tree[2 * i + 1]); } } // Update the value at position index to value void update(int index, int value) { index += n; tree[index] = value; while (index > 1) { index /= 2; tree[index] = min(tree[2 * index], tree[2 * index + 1]); } } // Query the minimum value in range [left, right] int query(int left, int right) { left += n; right += n + 1; int result = INT_MAX; while (left < right) { if (left % 2 == 1) { result = min(result, tree[left]); ++left; } if (right % 2 == 1) { --right; result = min(result, tree[right]); } left /= 2; right /= 2; } return result; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<int> data(n); for (int i = 0; i < n; ++i) { cin >> data[i]; } SegmentTree segTree(data); for (int i = 0; i < q; ++i) { int type; cin >> type; if (type == 1) { int k, u; cin >> k >> u; segTree.update(k - 1, u); } else if (type == 2) { int a, b; cin >> a >> b; cout << segTree.query(a - 1, b - 1) << '\n'; } } return 0; }
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: ACCEPTED
input |
---|
200000 200000 398739055 65343131 699208332 3... |
correct output |
---|
28609 129890 20378 20378 311522 ... |
user output |
---|
28609 129890 20378 20378 311522 ... Truncated |