ACM-ICPC 상 탈 사람

문제: icpc.me/15745 1~N 영역에 쌓인 눈의 높이가 주어진다. 이제 B개의 신발에 대한 쿼리가 들어오는데 각 쿼리는 Si와 Di를 가진다. Si는 해당 신발을 신고 걸을 수 있는 최대 눈의 높이이고, Di는 한번에 최대로 걸을 수 있는 거리이다. i번 째 신발을 신었을 때 1에서 부터 N까지 갈 수 있는 지 여부를 매 쿼리마다 출력해주면 되는 문제이다. 풀이법은 여러가지가 있는것 같지만 내가 푼 풀이는 오프라인 쿼리 풀이이다. 우선 쿼리를 Si기준으로 역순으로 정렬을 해준 뒤 순서대로 봐준다. 쿼리를 역순으로 본다면, 쿼리를 보면서 점점 못넘는 영역이 늘어날 것이다. 현재 쿼리를 처리할 때 넘을 수 있는 기준은 현재 못넘는 영역중에서 가장 긴 영역이 되므로 역순으로 쿼리를 처리하면서, 못넘는..

오늘은 disjoint set에 대해서 글을 적어보겠습니다. 직역하면 상호배타적 집합이며, union-find 라는 자료구조로 표현됩니다. [disjoint set, DSU(disjoint union),union find] 는 전부 union find 자료구조를 칭하는 말입니다. union find 는 union연산과 find연산을 매우 빠르게 해주는 자료구조로서, 상호배타 집합에서는 어떠한 집합에서도 공통 된 원소가 존재하지 않으며, 동시에 모든 집합의 합집합은 전체집합이 됩니다. 이해를 돕기 위하여 특수한 상황을 가정해보겠습니다. a라는 나라와 b라는 나라가 동맹이고, b라는 나라와 c라는 나라가 동맹을 맺게된다면 a와 c나라도 자동으로 동맹이 되는 경우를 생각해봅시다. 해당 경우로 각각의 나라의 동..