5209 : A10 - 리조트 호텔 (Resort Hotel)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
어떤 리조트 호텔에는 1호실부터 $N$ 호실까지 $N$ 개의 방이 있습니다. $i$ 호실은 $A_i$ 인용 방입니다.
이 호텔에서는 $D$ 일 동안 공사가 진행될 예정이며, $d$ 번째 날에는 $L_d$ 호실부터 $R_d$ 호실까지의 방을 사용할 수 없습니다.
$d=1, 2, \dots, D$ 에 대해, $d$ 번째 날에 사용할 수 있는 방 중에서 가장 큰 방은 몇 인용인지 출력하는 프로그램을 작성하세요.
[제약 조건]
• $3\le N\le 100000$
• $1\le D\le 100000$
• $1\le A_i\le 100$
• $2\le L_i\le R_i\le N - 1$
• 입력되는 모든 값은 정수입니다.
이 호텔에서는 $D$ 일 동안 공사가 진행될 예정이며, $d$ 번째 날에는 $L_d$ 호실부터 $R_d$ 호실까지의 방을 사용할 수 없습니다.
$d=1, 2, \dots, D$ 에 대해, $d$ 번째 날에 사용할 수 있는 방 중에서 가장 큰 방은 몇 인용인지 출력하는 프로그램을 작성하세요.
[제약 조건]
• $3\le N\le 100000$
• $1\le D\le 100000$
• $1\le A_i\le 100$
• $2\le L_i\le R_i\le N - 1$
• 입력되는 모든 값은 정수입니다.
입력 설명
$N$
$A_1$ $A_2$ $\dots$ $A_N$
$D$
$L_1$ $R_1$
$\dots$
$L_D$ $R_D$
$A_1$ $A_2$ $\dots$ $A_N$
$D$
$L_1$ $R_1$
$\dots$
$L_D$ $R_D$
출력 설명
$D$ 줄에 걸쳐 각 날짜별로 사용할 수 있는 최대 방 크기를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
1 2 5 5 2 3 1
2
3 5
4 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
5