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

Code

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

ull n, q;
ull ns[2*100000+1];
ull ts[2*2*100000+1];

// void create(){
//     for(ull k=1; k<=n; k=k<<1){
//         for(ull i=0; i<n-k+1; i++) {
//             ull a = i;
//             ull b = i + k;
//             ull ai = i - 
//             ts[i] = min(ts[2*i], ts[2*i+1]);
//         }
//     }
// }

int main(){
    std::cin >> n >> q;
    for(ull i=0; i<n; i++){
        ull nn;
        cin >> nn;
        ns[i] = nn;
        ts[i+n] = nn;
    }
    
    for(ull i=n-1; i>0; i--){
        ts[i] = min(ts[2*i], ts[2*i+1]);
    }

    for(ull i=0; i<q; i++){
        ull t, a, b;
        cin >> t >> a >> b;
        if(t == 1){
            // ns[a-1] = b;
            ull k = a+n-1;
            ts[k] = b;
            k>>=1;
            for(; k>1; k>>=1){
                ts[k] = min(ts[2*k], ts[2*k+1]);
            }
        }
        else{
            // ull minval = *min_element(ns.begin()+(a-1), ns.begin()+(b));
            // cout << minval << endl;
            ull a2 = a+n-1;
            ull b2 = b+n-1;
            ull r = ULLONG_MAX;
            for(; a2<=b2; a2/=2, b2/=2){
                if(a2%2){
                    r = min(r, ts[a2]);
                    a2++;
                }
                if(!(b2%2)){
                    r = min(r, ts[b2]);
                    b2--;
                }
            }
            cout << r << endl;
        }
    }
}

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