KOI 2014 - 버스

http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=2796
에서 채점할 수 있다. (File IO를 사용하니 입출력에 유의하라)

3달 전 본선에서 풀려 했을 때는 m^2를 짜고 최적화를 하면 될 줄 알았는데

전혀... 그런 풀이가 아니었다 ㅋㅋㅋ

나온 다음에, 정렬 하는거 까지는 눈치챘지만 그 이후 아이디어는 잘못 생각했었음..

얼마 전에 다시 생각해봤는데 풀이는 간단하다.

먼저 버스의 시작점 순으로 소트한 다음에, 시작점이 전 원소보다 큰데 끝 점이 전 원소보다 작은 경우는 존재하지 않는다는 것을 알면 된다.

결과적으로 실제 버스의 집합은 시작점과 끝 점 모두가 증가하는 형태일 것이다.

그렇기때문에 시작점 순으로 버스를 쭉 넣은 다음에... 만약에 현재 버스 집합의 최종 끝점이 자신보다 작으면 이번 버스는 누군가에 속하는 거고, 버스 집합에 넣지 않으면 된다.

(아, 그리고 시작점이 같은 쿼리에 대해서는 어떻게 정렬해야 할까?)

원 처리 역시 간단하게 가능하다.

뒷점 > 앞점으로 가는 버스에 경우 뒷점 -> 앞점 + N 으로 가는 버스라고 생각하면 된다.

그러면 위 상황과 똑같이 처리가능하다.

하지만, 이 경우 앞에 있는 버스의 일부는 뒤에 추가된 버스에 의해서 사라질 것이다.

즉, 뒤에 추가된 버스 중 끝점이 가장 큰 놈 보다, 앞에 있는 버스들의 끝점이 작다면, 이들은 버스 집합에 들어가지 않는다.

이를 알면 간단히 구현할 수 있다.

다만 정답을 번호 순대로 출력하기 위해서는 다시 번호 순으로 정렬해서 출력해야 할 것이다.

본인은 deque를 써서 구현했는데, 입맛대로 하면 된다.

예제 소스 : http://pastebin.com/CkVLG5u3