Algo O(nm) works for 1.046 sec,
but O(2n) uses more than 65536kb.


Edited by author 02.01.2014 15:28

1.031 for O(NxM) with pre-exit after left coordinate of segment > coordinate of point.
Any idea for modifications?

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.

Well, okay, there is a O(mlogn) solution with sorting only and 0.125s execution time.

Can you please write some more details for sorting based algorithm?

I think you can search for red-black trees algo, it has O(nlogm) but its realy hard as for me.

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

FUCKING PIGS SUCK A DICK

Since the input is sorted already, there is a O(n+m) solution