Submission #919113

#	Time	Username	Problem	Language	Result	Execution time	Memory
919113		andre4lc	Deda (COCI17_deda)	C++14	140 / 140	73 ms	8932 KiB

deda

#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 / 140