세그먼트 트리 기본만 할 줄 알아도 풀만한가요?
10732번 - 소방차게임
세그먼트 트리 기본만 할 줄 알아도 풀만한가요?
머리로는 풀었는데 시간복잡도가 O(TNNlogN) 맞나요? 뭔가 너무 큰 거 같은데
세그트리는 안 써도 될 거 같은데... 풀어보겠습니다
각 선분마다 이벤트 정리 후 세그트리를 쓰거나 하는 방법이 아닌가 보네요? 잘못 푼 거 같기도 하고....
멀티 소스 데이크스트라에 QNlogV면 맞게 풀긴 한 거 같은데 아무튼 풀어보죠. 감사합니다.
까짓 거 해보죠
교점들을 노드로 하니까 정점이 100만개인데 정점 개수를 N개로 줄여서 푸는 방법이 있나요?
아하
코드 읽어봤는데 세그먼트트리를 사용해서 어떤 걸 최적화한 건가요? 지금 제 코드보다 빠른 방법이 있나 생각해보는 중입니다
댓글을 작성하려면 로그인해야 합니다.
kjk9704 1년 전 5
2015년 5월 13일 마지막으로 왜 이 문제가 안 풀리는지 알 것 같군요.
이 문제는 그저 선분 교차 + 데이크스트라 1번만 하면 될 줄 알았는데 설마 세그먼트 트리가 필요할 줄은 전혀 몰랐습니다.
(에디토리얼에서는 안 적혀 있습니다.)
그래서 구현하는데 꽤 많은 애를 먹었고 이 문제보다 더 어렵다고 판단하여 루비 5로 측정했습니다.
다이아 1티어로 줄까 고민하다가 선분 교차 + 데이크스트라 + 세그먼트 트리 + 오프라인 쿼리가 동시에 나오는 문제가 다이아 구간에 존재하지 않으므로 루비 문제로 판단합니다.
어쨋거나 2025년 11월 10일, 10년 만에 이 문제가 풀렸습니다.
[2025-11-11 12:25]
세그먼트 트리 없이도 구현되는 것을 보고 아무래도 제가 Python 구현하는 과정에서 세그먼트 트리로 더 최적화를 했나 봅니다.
[2025-11-11 20:16]
에디토리얼이 이미 존재하고 제가 알고리즘 태그들을 만들면서 힌트가 존재하는 상태이며 세그먼트 트리가 강요되지 않아 이 문제는 루비 급이 아닌 것으로 판단, 다이아 1티어 혹은 2티어가 적당하나 저는 개인적으로 다이아 1티어로 내릴 생각입니다.