ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1112. Cover

WA #8
Posted by Anna Tokhyan 11 Jul 2017 03:14
Does anyone know the 8th test?
Re: WA #8
Posted by Mahilewets 18 Jul 2017 17:54
The test is such an input  data
That if the program behaves as burunduk1 described in his habrahabr.ru post from 2015
It passes the test
(And all others tests too)
Re: WA #8
Posted by Mahilewets 18 Jul 2017 17:58
So,  sort intervals according to RIGHT endpoints in non-decreasing order.

Consider intervals in the sorted order.

Let M=max of all right ends added so far.

Then if current left end is not less than M then add current interval to answer  and update M if current right end is greater than M.
Re: WA #8
Posted by Anna Tokhyan 20 Jul 2017 23:59