https://codeforces.com/contest/1741/problem/F
Problem - F - Codeforces
codeforces.com
어떤 막대기 a, b가 있을 때 거리가 max(0, a.l - b.r) 로 구해지는 경우를 생각해보자.
막대기 a에 대해 b.l <= a.r 인 모든 막대기 b 중에서 a 와 다른 색인 경우에 거리를 계산하면 된다.
r기준 오름차순으로 정렬된 배열과 인덱스 i, l기준 오름차순으로 정렬된 배열과 인덱스 j 가 있을 때
r을 순회할 때마다 j.l <= i.r 을 만족하지 않을 때 까지 j를 증가시키면서 해당하는 막대기의 r과 c를 저장해주면 된다.
그 다음 그 저장된 막대기 중에서 i 막대기와 색이 다르며 r이 가장 큰 것을 골라서 거리를 계산하면 된다.
이 때, 막대기는 사실 전부 저장할 필요 없이 최대 서로 다른 색 막대기 2개까지만 관리해주면 되는 것을 확인할 수 있다.
거리를 max(0, b.r - a.l) 로 구하는 경우는 (l, r) => (-r, -l) 로 바꾼 뒤 위의 방법을 그대로 적용하면 된다.