Task: | Dynamic Range Minimum Queries |
Sender: | fabiank |
Submission time: | 2024-09-23 13:06:46 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.46 s | details |
Compiler report
input/code.cpp: In function 'std::vector<int> create_segment_tree(std::vector<int>&, int)': input/code.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 53 | for (int i = 0; i < values.size(); i++) | ~~^~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h> using namespace std; vector<int> create_segment_tree(vector<int> &values, int n); void update_segment_tree(vector<int> &seg_tree, int i, int u, int n); int query_segment_tree(vector<int> &seg_tree, int a, int b, int n); int next_power_2(int x); void print_vector(vector<int> &x); // approach: SegmentTrees int main() { int n, q; cin >> n >> q; vector<int> values(n); for (int i = 0; i < n; i++) { cin >> values[i]; } int seg_tree_n = next_power_2(n); vector<int> seg_tree = create_segment_tree(values, seg_tree_n); for (int i = 0; i < q; i++) { int type; cin >> type; if (type == 1) { int k, u; cin >> k >> u; k--; update_segment_tree(seg_tree, k, u, seg_tree_n); } else { int a, b; cin >> a >> b; a--; b--; int query_result = query_segment_tree(seg_tree, a, b, seg_tree_n); cout << query_result << "\n"; } } } vector<int> create_segment_tree(vector<int> &values, int n) { vector<int> seg_tree(2 * n, INT32_MAX); for (int i = 0; i < values.size(); i++) { seg_tree[n + i] = values[i]; } for (int i = n - 1; i > 0; i--) { seg_tree[i] = min(seg_tree[2 * i], seg_tree[2 * i + 1]); } return seg_tree; } void update_segment_tree(vector<int> &seg_tree, int i, int u, int n) { // print_vector(seg_tree); int k = i + n; // cout << "i: " << i << " - u: " << u << " - n: " << n << " - k: " << k << endl; seg_tree[k] = u; for (k /= 2; k >= 1; k /= 2) { // cout << "k: " << k << endl; // print_vector(seg_tree); seg_tree[k] = min(seg_tree[2 * k], seg_tree[2 * k + 1]); } } int query_segment_tree(vector<int> &seg_tree, int a, int b, int n) { a += n; b += n; int result = INT32_MAX; while (a <= b) { if (a % 2 == 1) { result = min(result, seg_tree[a++]); } if (b % 2 == 0) { result = min(result, seg_tree[b--]); } a /= 2; b /= 2; } return result; } int next_power_2(int x) { // int exponent = ceil(log2(x)); // return pow(2, exponent); int power_2 = 1; while (power_2 <= x) { power_2 = power_2 << 1; } return power_2; } void print_vector(vector<int> &x) { for (int v : x) { cout << v << " "; } cout << "\n"; }
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 |