Nov 2020
1 / 9
Nov 2020
Dec 2020
simes
Nov '20

Here’s one. Expected answer is 3, your answer is 2.

1
5
2 3
5 6
2 4
3 5
4 7

flash_nil
Dec '20
1

Thank You for your reply.

I have solved that issue and used multimap

As we know, map has a complexity of insertion and deletion is O(1) and binary search has a complexity of O(logn).

My code has a complexity of O(nlog(n)). Then why it is giving TLE ?

My solution: https://pastebin.ubuntu.com/p/TnV9f9HMqt/4

simes
Dec '20

There are two problems that I can see. Either alone means that a simple test case with 5 lines exceeds the 15 seconds runtime allowed on ideone.

What does this do, and why might it cause a problem?

what may happen to the iterator here?

flash_nil
Dec '20

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

I have used it for faster input output though i’ve used scanf prinf. Link1

tFinish_idx.erase(it)

It is for erasing finish time from the multimap. Editing map’s index is not valid. So i erased it first then inserted it with new finishing time .

simes
Dec '20

What shouldn’t you do after using ios::sync_with_stdio(0)?

And what may happen to the iterator after using tFinish_idx.erase(it)?

flash_nil
Dec '20

ios::sync_with_stdio(0)

this has no use here. So we can remove this.

tFinish_idx.erase(it)

this will delete the previous finishing time of a lecture in determined room.

simes
Dec '20

You are using both cin and scanf - so what effect does ios::sync_with_stdio(0) have on that? The answer is that n would get some very strange values, far larger than you might expect.

I know why you’re using tFinish_idx.erase(it), but you’re not answering the question - what may happen to the ITERATOR after using using it? See www.cplusplus.com/reference/map/multimap/erase/. Iterators, pointers and references referring to elements removed by the function are invalidated. The iterator is invalidated, but you still continue to use it.

flash_nil
Dec '20

Thank you for your reply. This time, I’ve found out my mistake, Thanks a lot. I’ve learned a new thing from here.

Will it be the same O(n^2), if i use priority queue and erase function here?