Task: | Dynamic Range Minimum Queries |
Sender: | aarol |
Submission time: | 2024-09-22 17:58:50 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.26 s | details |
Code
#include <bits/stdc++.h> using namespace std; int n; int tree_min(vector<int> &tree, int a, int b) { a += n; b += n; int m = 1e9+5; while (a <= b) { if ((a % 2) == 1) { m = min(m, tree[a]); a++; } if ((b % 2) == 0) { m = min(m, tree[b]); b--; } a /= 2; b /= 2; } return m; } void update(vector<int> &tree, int i, int v) { i += n; tree[i] = v; int newMin; while (i > 1) { i /= 2; newMin = min(tree[2 * i], tree[2 * i + 1]); if (tree[i] != newMin) { tree[i] = newMin; } else return; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin >> n >> q; auto values = vector<int>(n); for (int i = 0; i < n; i++) { cin >> values[i]; } int tree_size = 2 * n; auto tree = vector<int>(tree_size, 1e9+5); for (int i = n; i < tree_size; i++) { tree[i] = values[i - n]; } for (int i = n - 1; i > 0; i--) { tree[i] = min(tree[2 * i], tree[2 * i + 1]); } for (int i = 0; i < q; i++) { int type, a, b; cin >> type >> a >> b; if (type == 1) { // update value at a to b update(tree, a - 1, b); } else { // query [a,b] cout << tree_min(tree, a - 1, b - 1) << endl; } } }
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 |