Task: | Dynamic Range Minimum Queries |
Sender: | aarol |
Submission time: | 2024-09-22 16:16:15 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | details |
#2 | WRONG ANSWER | 0.45 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:66:24: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare] 66 | for (size_t i = 0; i < n; i++) { | ~~^~~
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 = 2e6 + 5; while (a < b) { if ((a & 1) == 1) { m = min(m, tree[a]); a++; } if ((b & 1) == 1) { b--; m = min(m, tree[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; } } void build(vector<int> &tree, vector<int> &input, int node, int left, int right) { if (left == right) { tree[node] = input[left]; return; } else { int mid = (left + right) / 2; build(tree, input, 2 * node, left, mid); build(tree, input, 2 * node + 1, mid + 1, right); tree[node] = min(tree[2 * node], tree[2 * node + 1]); } } int p(int k) { return k & (-k); } int main() { // ios::sync_with_stdio(false); // cin.tie(0); int q; cin >> n >> q; auto values = vector<int>(n); for (size_t i = 0; i < n; i++) { cin >> values[i]; } int tree_size = 4 * n; auto tree = vector<int>(tree_size + 1, -1); build(tree, values, 1, 0, n - 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: WRONG ANSWER
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 |
---|
2000005 7 6 4 4 ... Truncated |
Test 2
Verdict: WRONG ANSWER
input |
---|
200000 200000 398739055 65343131 699208332 3... |
correct output |
---|
28609 129890 20378 20378 311522 ... |
user output |
---|
-1 65721 59886 -1 -1 ... Truncated |