Educational codeforces #78 D - Segment Tree (라인스위핑)
https://codeforces.com/contest/1278/problem/D 풀이가 너무 생소해서 정리해둠 최대 5e5개의 정점이 입력된다. 정점은 [l,r]의 정보를 담고 있다. 서로 교차되는(intersect) 정점들이 서로 이어져있다고 할 때, 그 그래프가 트리인지 아닌지를 출력하는 문제. ex) 정점[1,3]과 [2,4]는 이어져있다. 하지만 [1,2],[3,4]는 이어져 있지 않다. +모든 끝점은 유일하다. 예를들어 [1,2][2,3]이 동시에 주어지는 경우는 없다 1. 각 정점의 정보를 P a[MAX]에 담아둔다. 2. vector evs에 (a[i].first, i) 와 (a[i].second, i)를 모두 담아서 오름차순 정렬한다. 3. set cand를 마련한다. (아직 교차할 정점..
2019. 12. 29.
