oj.uz

Submission #919113

# Submission time Handle Problem Language Result Execution time Memory
919113 2024-01-31T10:13:29 Z andre4lc Deda (COCI17_deda) C++14
140 / 140
 73 ms 8932 KB 
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull STsize;
class STmimx{ 
    private:
        vector<ull> seg;
        void pushUp(ull node){
            seg[node]=min(seg[node*2],seg[node*2+1]);
        }
    public:
        void build(ull node=1,ull l=0,ull r=STsize-1){
            if(node==1){ seg.resize(2*pow(2,floor(log2(STsize))+1),LLONG_MAX); }
        }
        void update(ull i,ull v,ull node=1,ull l=0,ull r=STsize-1){
            if(l==r){
                seg[node]=v;
                return;
            }
            ull m=(l+r)/2;
            if(i<=m) update(i,v,node*2,l,m);
            else update(i,v,node*2+1,m+1,r);
            pushUp(node);
        }
        ull query(ull minChild,ull maxStation,ull node=1,ull l=0,ull r=STsize-1){
            if(r<minChild || maxStation<seg[node]) return 0;
            if(l==r){ return l+1; }
            ull lv=query(minChild,maxStation,node*2,l,(l+r)/2);
            if(lv) return lv;
            ull rv=query(minChild,maxStation,node*2+1,(l+r)/2+1,r);
            if(rv) return rv;
            return 0;
        }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ull ni; int nq; cin>>ni>>nq; STsize=ni;
    STmimx st; st.build();
    for(int q=0;q<nq;q++){
        char code; cin>>code;
        if(code=='M'){
            ull stop,child; cin>>stop>>child;
            st.update(child-1,stop);
        }
        else{
            ull maxStation,minChild; cin>>maxStation>>minChild;
            ull ans=st.query(minChild-1,maxStation);
            if(ans) cout<<ans<<'\n';
            else cout<<-1<<'\n';
        }
    }
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 59 ms 8932 KB Output is correct
5 Correct 64 ms 6480 KB Output is correct
6 Correct 71 ms 8744 KB Output is correct
7 Correct 73 ms 8780 KB Output is correct