nuradil's blog

Why my solution got TL?
By nuradil, history, 10 years ago, In English

Why my solution for this problem got TL?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

i am getting TLE on the same test case . My soln : http://codeforces.me/contest/749/submission/23175411

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it 
    for(int i = 0;i<bi[x].size();++i){
	mms.erase(bi[x][i]);
}

    It works O(N) on worst case, so in total it will be O(N * Q * log(N)).

    → Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
vector <pii> mx;
res = *lower_bound (mx.begin(), mx.end(), make_pair (key, 0));

I hear that complexity of lower_bound is O(n) for some cases.

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it 
vector <pii> mx;
mx = vec[t[1].S];

It works O(size), that's why you got tle. Try using references.

→ Reply