시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 27 | 10 | 9 | 64.286% |
$N$ 명의 사람이 원형으로 앉아 게임을 한다. 사람들은 시계 방향 순서대로 $1$번부터 $N$번까지 번호가 붙어 있다.
첫 번째 라운드에는 모든 사람이 게임에 참가하지만 다음 $M$번의 추가 라운드 동안 다음 $3$가지 쿼리 중 하나로 참여하는 사람의 인원이 변한다.
구간에 속하지 않은 사람은 이전 라운드에 참여했다면 다음 라운드에 참여하고, 참여하지 않았다면 다음 라운드에 참여하지 않는다.
인접한 두 사람의 실력 차가 작을수록 더 즐겁게 게임을 즐길 수 있으므로 라운드마다 인접한 두 사람의 실력 차 중 최댓값을 구해 게임의 재미를 구하려고 한다.
한 라운드에 참여하는 사람이 $1$명 이하라면 실력 차이가 발생할 수 없으므로 실력 차는 $0$이다.
첫째 줄에 사람의 수 $N$과 추가 라운드의 수 $M$이 주어진다. ($2 \leq N \leq 200\,000$, $1 \leq M \leq 200\,000$)
둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. 이는 $i$번 사람의 실력이 $A_i$라는 것을 의미한다. ($1 \leq A_i \leq 10^9$)
셋째 줄부터 $M$개의 줄 중 $i$ 번째 줄에는 쿼리의 번호 $x_i$, 구간을 의미하는 $l_i$와 $r_i$가 공백으로 구분되어 주어진다. ($1 \leq x_i \leq 3$, $1 \leq l_i, r_i \leq N$)
$l_i \leq r_i$ 인 경우, $l_i \leq j \leq r_i$를 만족하는 $j$번 사람이 구간에 포함된다는 것을 의미하고, $l_i > r_i$인 경우, $1 \leq j \leq r_i$ 혹은 $l_i \leq j \leq N$을 만족하는 $j$번 사람이 구간에 포함된다는 것을 의미한다.
입력으로 주어지는 모든 수는 정수이다.
첫째 줄에 모든 사람이 참여했을 때의 인접한 두 사람의 실력 차 중 최댓값을 출력한다.
다음 $M$개의 줄에 라운드마다 인접한 두 사람의 실력 차 중 최댓값을 출력한다.
4 4 1 2 6 3 1 3 3 3 2 4 3 2 1 2 1 1
4 2 5 1 2
Camp > 숭고한 연합 Algorithm Camp > 2022 숭고한 연합 알고리즘 콘테스트 > Division 2 H번