Task: | Dynamic Range Minimum Queries |
Sender: | snude |
Submission time: | 2024-09-22 20:39:33 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | WRONG ANSWER | 0.45 s | details |
Code
#include <algorithm> #include <climits> #include <cstdio> #include <iostream> #include <vector> using namespace std; int get_min(int a, int b, vector<int> &tree, int n) { a += n; b += n; int s = INT_MAX; while (a <= b) { if (a%2 == 1) s = min(tree[a++], s); if (b%2 == 0) s = min(tree[b--], s); a /= 2; b /= 2; } return s; } void update(int k, int x, vector<int> &tree, int n) { k += n; tree[k] = x; for (k /= 2; k >= 1; k /= 2) { tree[k] = min(tree[2*k], tree[2*k+1]); } } int bit_ceil(int n) { int res = 1; while (res < n) res <<= 1; return res; } vector<int> create_segment_tree(int n, vector<int> &input) { int size = bit_ceil(n); vector<int> tree(2 * size, INT_MAX); // Add input to the end for (int i = 0; i < n; i++) { tree[size + i] = input[i]; } // start from the end, from the second last element -> -2 for (int i = size * 2 - 2; i > 0; i -= 2) { tree[i/2] = min(tree[i], tree[i + 1]); } return tree; } int main(int argc, char *argv[]) { // Read the input parameters int n, q; cin >> n >> q; // Read values from one line vector<int> input_line(n); for (int i = 0; i < n; i++) { cin >> input_line[i]; } vector<int> segment_tree = create_segment_tree(n, input_line); for (int i = 0; i < q; i++) { int type, first, second; cin >> type >> first >> second; // I use zero based indexing, second must be reduced only when querying first--; if (type == 1) { update(first, second, segment_tree, n); } else if (type == 2) { second--; cout << get_min(first, second, segment_tree, n) << "\n"; } } // for (int i = 0; i < 16; i++) { // cout << segment_tree[i] << " "; // } 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: WRONG ANSWER
input |
---|
200000 200000 398739055 65343131 699208332 3... |
correct output |
---|
28609 129890 20378 20378 311522 ... |
user output |
---|
12643 2147483647 28609 28609 12643 ... Truncated |