cbertake's blog

Help in finding TLE
By cbertake, history, 3 hours ago, In English

Can anyone tell me why is this giving TLE whereas the editorial code is basically the same. What's the issue here? My Code:

ll do_it(ll x){ ll ret=0; while(x>0){ ret+=x%10; x/=10; } return ret; } void solve(){ ll n,q;cin>>n>>q; ipar(a,n); setact;

for(int i=0;i<n;i++){
    if(a[i]>9)
        act.insert(i);
}
while(q--){
    ll c;cin>>c;
    if(c==1){
        ll l,r;cin>>l>>r;
        l--;r--;
        ll lst=l;
        while(!act.empty()){
            auto it=lower_bound(all(act),lst);///element which is >=l

            if(it==act.end() || *it>r)
                break;
            a[*it]=do_it(a[*it]);
            ll cur=*it;
            act.erase(it);
            if(a[cur]>9)///this reduces the size of act without need of cntop vector
                act.insert(cur);///a[cur] will alwasy eb less than original
            lst=cur+1;///it could happen that the processed elemtn enter at same place
            ///so increment lst to avoid double processing
        }
    }else {
        ll x;cin>>x;
        --x;
        cout<<a[x]<<"\n";
    }
}

}

Problem Link: https://mirror.codeforces.com/contest/1791/problem/F Editorial: https://mirror.codeforces.com/blog/entry/112282

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

lower_bound(set.begin(), set.end(), x) is slow.
use set.lower_bound(x) instead

→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks i didn't knew this.

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

act.lower_bound(lst) is O(log(n))

lower_bound(all(act),lst) is O(n)

→ Reply