CSES - Aalto Competitive Programming 2024 - wk4 - Homework - Results
Submission details
Task:Dynamic Range Minimum Queries
Sender:laluj
Submission time:2024-09-23 20:06:59 +0300
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.45 sdetails

Compiler report

input/code.cpp: In function 'int minq(int, int)':
input/code.cpp:11:9: warning: unused variable 'ta' [-Wunused-variable]
   11 |     int ta=a,tb=b;
      |         ^~
input/code.cpp:11:14: warning: unused variable 'tb' [-Wunused-variable]
   11 |     int ta=a,tb=b;
      |              ^~
input/code.cpp: In function 'void update(int, int)':
input/code.cpp:23:9: warning: unused variable 't' [-Wunused-variable]
   23 |     int t = k;
      |         ^
input/code.cpp: In function 'int main()':
input/code.cpp:36:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
input/code.cpp:44:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     for (size_t i = 0; i < q; i++)
      |                        ~~^~~

Code

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << ": " << x << endl;

int n;
vector<int> tree;

int minq(int a, int b) {
    int ta=a,tb=b;
    a += n; b += n;
    int m = numeric_limits<int>::max();
    while (a <= b) {
        if (a%2 == 1) m = min(m,tree[a++]);
        if (b%2 == 0) m = min(m,tree[b--]);
        a /= 2; b /= 2;
    }
    return m;
}

void update(int k, int x) {
    int t = k;
    k += n;
    tree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = min(tree[2*k],tree[2*k+1]);
    }
}

int main() {
    int q;
    cin >> n >> q;
    tree.resize(2*n);

    for (size_t i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        update(i, x);
    }

    int queries[q][3];
    for (size_t i = 0; i < q; i++)
    {
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    }
    
    for (auto &&quer : queries)
    {
        if (quer[0] == 1) update(quer[1]-1, quer[2]);
        else cout << minq(quer[1]-1, quer[2]-1) << 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