Informatica Online Judge

  구간 최댓값 [1919 / 077F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 33   Total Tried : 52


The Champion of this Problem (C++) : koi17031 - 0ms / 484byte
My Best Submission (C++) : N/A

[koistudy.net (JKJeong)]

Background

n개의 자료를 가지는 배열에서

주어진 구간 [l, r]의 최댓값을 구하는 q개의 질문이 입력된다.

각 질문은 주어진 폐구간에서 가장 큰 값을 찾는 것이다.

각 q개의 질문에 대해서 빠르게 답을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n, q가 공백으로 구분되어 입력된다.

두 번째 줄에 n개의 자료가 공백으로 구분되어 입력된다.

다음 줄부터 q줄에 걸쳐서 l, r이 공백으로 구분되어 한 줄에 하나씩 입력된다.

[입력값의 정의역]
1 <= n <= 100,000
1 <= q <= 100,000
1 <= l <= r <= n
-1,000 <= 각 원소 <= 1,000

Output

각 q개의 질문에 대해서 구간의 최댓값을 한줄에 하나씩 출력한다.

IO Example

입력
5 3
1 2 3 4 5
1 2
3 4
1 5

출력
2
4
5

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]