Submission #917978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917978	2024-01-29T08:59:15 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	281 ms	7764 KB

deda

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const int N = 2e5 + 37;
const ll inf = 1e17 + 37;
int n, q;
struct SegmentTree{
    ll t[4 * N];
    
    SegmentTree() {
        for(int i = 0; i < 4 * N; ++i)
            t[i] = inf;
    }

    void update(int idx, int val, int v = 1, int l = 1, int r = n){
        assert(l <= r);
        if(idx < l or r < idx)
            return;
        if(l == r){
            assert(l == idx);
            t[v] = val;
            return;
        }
        int m = (l + r) / 2;
        if(idx <= m)
            update(idx, val, v * 2, l, m);
        else
            update(idx, val, v * 2 + 1, m + 1, r);
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }

    ll wolk_dat_tree(int max_dur, int v, int l, int r){
        if(l == r){
            assert(t[v] <= max_dur);
            return l;
        }
        int m = (l + r) / 2;
        if(t[v * 2] <= max_dur){
            return wolk_dat_tree(max_dur, v * 2, l, m);
        }
        else if(t[v * 2 + 1] <= max_dur){
            return wolk_dat_tree(max_dur, v * 2 + 1, m + 1, r);
        }
        else
            return inf;
    }

    ll query(int min_age, int max_dur, int v = 1, int l = 1, int r = n){
        if(r < min_age or t[v] > max_dur)
            return inf;
        if(min_age <= l){
            return wolk_dat_tree(max_dur, v, l, r);
        }

        int m = (l + r) / 2;
        return min(query(min_age, max_dur, v * 2, l, m), 
                   query(min_age, max_dur, v * 2 + 1, m + 1, r));
        
    }

};      

void solve(void){
    cin >> n >> q;
    SegmentTree t;
    while(q--){
        char qt;
        cin >> qt;
        if(qt == 'M'){
            int len, child;
            cin >> len >> child;
            t.update(child, len);
        }
        else{
            int min_age, max_dur;
            cin >> max_dur >> min_age;
            ll ans = t.query(min_age, max_dur);
            if(ans == inf)
                ans = -1;
            cout << ans << endl;
        }
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // int t; cin >> t; while(t--) 
        solve();
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6488 KB	Output is correct
2	Correct	6 ms	6488 KB	Output is correct
3	Correct	12 ms	6492 KB	Output is correct
4	Correct	280 ms	7764 KB	Output is correct
5	Correct	233 ms	7252 KB	Output is correct
6	Correct	281 ms	7428 KB	Output is correct
7	Correct	271 ms	7612 KB	Output is correct