CSES - Aalto Competitive Programming 2024 - wk4 - Homework - Results
Submission details
Task:Dynamic Range Minimum Queries
Sender:aarol
Submission time:2024-09-22 16:16:15 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.45 sdetails

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:

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:

input
200000 200000
398739055 65343131 699208332 3...

correct output
28609
129890
20378
20378
311522
...

user output
-1
65721
59886
-1
-1
...
Truncated