nuradil's blog

By nuradil, history, 8 years ago, In English

Why my solution for this problem got TL?

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

| Write comment?
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      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)).

»
8 years ago, # |
  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.

»
8 years ago, # |
  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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Ty mate!!! Lost about day for searching mistake.