https://www.acmicpc.net/problem/13334

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


abs(h_i - o_i) <= L인 경우에 대해서만 입력을 받음 ( abs(h_i - o_i) > L 이면 어차피 답에 포함이 안 되니) 얘네들의 개수 = n'


h_i, o_i 중에 더 작은 걸 left벡터에, 더 큰 걸 right벡터에 저장 후 둘 다 정렬


L의 시작점을 left의 가장 작은 원소부터 하나씩 증가시켜가며 탐색, 즉 시작점 = left[i], 끝나는 점 = left[i] + d


a = left에서 left[i]보다 작은 원소의 개수 = left[i]보다 왼쪽에서 시작하는 선분들의 개수

 b = right에서 left[i]+d보다 큰 원소의 개수 (이분탐색) = left[i]+d보다 오른쪽에서 끝나는 선분들의 개수


d보다 긴 선분들은 다 제외했기 때문에 a, b에서 카운트되는 애들은 다 L 밖에 있거나 L의 시작점이나 끝점에 걸치는 선분들


따라서 n' - a - b의 최대값이 정답 (시간복잡도: nlogn)