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
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.