8022 : 트래픽 라이트
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
길이가 $X$인 직선 도로가 있습니다. 도로의 시작점은 $0$, 끝점은 $X$입니다.
이 도로의 서로 다른 위치에 순서대로 $N$개의 신호등이 설치됩니다.
각 신호등이 설치될 때마다, 신호등이 없는 도로 구간 중에서 가장 긴 구간의 길이를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le X \le 10^9$
• $1 \le N \le 2 \times 10^5$
• $0 < p_i < X$ (신호등 설치 위치는 모두 서로 다름)
이 도로의 서로 다른 위치에 순서대로 $N$개의 신호등이 설치됩니다.
각 신호등이 설치될 때마다, 신호등이 없는 도로 구간 중에서 가장 긴 구간의 길이를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le X \le 10^9$
• $1 \le N \le 2 \times 10^5$
• $0 < p_i < X$ (신호등 설치 위치는 모두 서로 다름)
입력 설명
첫째 줄에 도로의 길이 $X$와 신호등의 개수 $N$이 공백으로 구분되어 주어집니다.
둘째 줄에 각 신호등이 설치될 위치 $p_1, p_2, \ldots, p_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 각 신호등이 설치될 위치 $p_1, p_2, \ldots, p_N$이 공백으로 구분되어 주어집니다.
출력 설명
각 신호등이 설치될 때마다 가장 긴 구간의 길이를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8 3
3 8 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3 3도움
신호등 위치들을 저장하는 균형 이진 탐색 트리(
신호등 $p$가 추가되면 $p$의 직전 위치 $L$과 직후 위치 $R$을 찾아 기존 구간 길이 $(R-L)$을 멀티셋에서 삭제하고, 두 개의 새 구간 $(p-L)$과 $(R-p)$를 삽입한 뒤 멀티셋의 최댓값을 출력합니다. (각 단계 $O(\log N)$)
std::set)와 각 구간의 길이들을 저장하는 멀티셋(std::multiset)을 함께 운영합니다.신호등 $p$가 추가되면 $p$의 직전 위치 $L$과 직후 위치 $R$을 찾아 기존 구간 길이 $(R-L)$을 멀티셋에서 삭제하고, 두 개의 새 구간 $(p-L)$과 $(R-p)$를 삽입한 뒤 멀티셋의 최댓값을 출력합니다. (각 단계 $O(\log N)$)