17266 어두운 굴다리

공유기 설치와 유사한 문제, 파라메트릭 서치를 통해서 구할 수 있다

주의할 점이 2개가 있다

1. N = 100000으로 반드시 NlgN으로 해결해야 한다. 파라메트릭 서치에서 lgN으로 해결한다면, 검사를 반드시 N으로 끝내야만 한다. 그런데 하나씩 모두 값을 채워넣는다면 불가능하고, 좌표 N만큼 돌리면서 '범위' 안에만 있다는 것만 확인하면 된다

 

2. 만일 전 가로등에서 해당 좌표를 밝히지 못한다면, 다음 좌표는 해당 좌표 전의 좌표부터 포함해야만 한다. 사잇값을 비워두면 안되기 때문이다

 

문제: https://www.acmicpc.net/problem/17266

https://github.com/surinoel/boj/blob/master/17266.cpp