Task: | Dynamic Range Minimum Queries |
Sender: | hungdojan |
Submission time: | 2024-09-22 02:44:00 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.27 s | details |
Code
#include <bits/stdc++.h> using namespace std; #define PRINT_ARR(arr, n) \ do { \ for (int i = 0; i < n; i++) { \ cout << arr[i] << " "; \ } \ cout << "\n"; \ } while (0) #define DEF_VAL LONG_LONG_MAX typedef long long ll; int max_exp(int a, int b) { int diff = b - a + 1; int exp; for (exp = 0; diff >>= 1; exp++) ; return exp; } void s_update(int k, ll value, ll *arr, int size) { k += size / 2 - 1; arr[k] = value; for (k /= 2; k >= 1; k /= 2) { arr[k] = min(arr[2 * k], arr[2 * k + 1]); } } ll s_min(int a, int b, ll *arr, int size) { a += size / 2 - 1; b += size / 2 - 1; ll s = arr[0]; while (a <= b) { if (a % 2 == 1) s = min(s, arr[a++]); if (b % 2 == 0) s = min(s, arr[b--]); a /= 2; b /= 2; } return s; } void s_init(ll *arr, int size, int nof_elem) { int t; for (int i = 1; i <= nof_elem; i++) { cin >> t; s_update(i, t, arr, size); } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; int temp = max_exp(0, n - 1); temp = 1 << temp; if (temp < n) { temp <<= 1; } int size = temp * 2; ll arr[size]; for (int i = 0; i < size; i++) { arr[i] = DEF_VAL; } s_init(arr, size, n); int c, l, r; for (int i = 0; i < q; i++) { cin >> c >> l >> r; if (c == 1) { s_update(l, r, arr, size); } else { cout << s_min(l, r, arr, size) << endl; } } 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 |