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

Discussion of Problem 1987. Nested Segments

i'm sad
Posted by Two-Eight-Nine [[ §289]] 2 Jan 2014 15:27
Algo O(nm) works for 1.046 sec,
but O(2n) uses more than 65536kb.


Edited by author 02.01.2014 15:28
Re: i'm sad
Posted by Evgeniy_Chernobrovkin(MUCTR-2013) 21 Jan 2014 06:15
1.031 for O(NxM) with pre-exit after left coordinate of segment > coordinate of point.
Any idea for modifications?
Re: i'm sad
Posted by adamant 22 Jan 2014 16:37
0.625 for O(mlogn) solution using C++ STL set... I think the problem is harder, than its difficulty score if there is no easier solution.
Re: i'm sad
Posted by adamant 24 Jan 2014 14:18
Well, okay, there is a O(mlogn) solution with sorting only and 0.125s execution time.
Re: any detailed algorithm?
Posted by Nodir NAZAROV Komiljonovich 10 Feb 2014 21:47
Can you please write some more details for sorting based algorithm?
Re: any detailed algorithm?
Posted by Evgeniy_Chernobrovkin(MUCTR-2013) 21 Feb 2014 19:43
I think you can search for red-black trees algo, it has O(nlogm) but its realy hard as for me.
Small(?) hint
Posted by Leonid 14 Mar 2014 11:03
This problem can be solved fast, if you'll try not to consider common solution, but only this ( there is some useful limits in statement, also order is very convenient  ) case.
Small hint, that I promised: Imagine a big-length wall, like in old platformers, where segments are vertical levels and segment's coords are horizontal coords.
Example:
4
2 10
2 3
5 7
6 7

00000011000
00110111000
00111111111
1 are bricks in our wall.

Edited by author 14.03.2014 11:03
Re: Small(?) hint
Posted by a6 14 Mar 2014 13:38
FUCKING PIGS SUCK A DICK
Re: i'm sad
Posted by Dmytro Dziuma (DixonD) [Lviv NU] 24 Apr 2014 04:06
Since the input is sorted already, there is a O(n+m) solution