CSES - Aalto Competitive Programming 2024 - wk4 - Homework - Results
Submission details
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 results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.27 sdetails

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