SAT2020's blog

By SAT2020, history, 6 weeks ago, In English

Hello Codeforces friends,

I am currently befuddled by a TLE I received on Problem 365A, "Knight Tournament". Essentially, the problem provides the user with a series of range queries, Each range query represents a set of "knights" that participated in a "tournament round", with a "winning knight" conquering every other knight in the range. The problem asks the user to spit out a list of the conquerers of each knight. The critical difficulty is that multiple queries might have overlapping ranges. My solution was to keep a constantly updating set of knights in the tournament. Each time a knight was conquered, I'd remove them from the set. Unfortunately, while my solution passed the correctness tests, I got a TLE on test #11. Could anyone please tell me what I did wrong?

You can find my code here: https://codeforces.com/contest/356/submission/162602701

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

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Unfortunately, no one has replied, but I did figure out what went wrong, and I am posting it here in case others in the future are confused. For some reason, the command: lower_bound(set.begin(), set.end(), val) takes O(n) time, while set.lower_bound(val) only takes O(log(n)). From what I've seen online, this is because the compiler knows that when a programmer uses the second command, they're performing a binary search on a set, but with the first command, it's unclear which data structure is being used so a binary search is not feasible. Don't take my word for it though, this is just what I've seen random posters online say.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Segment tree can

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

use segment tree

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

you should use segment tree.