| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 5194 | 2578 | 2190 | 51.132% |
숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!
욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어 버렸다!! 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 Q개나 주어진다!! (ᄒᄒ;; ᄌᄉ.. ᄏᄏ!!)
Figure 1. 모든 참가자가 문제를 풀 수 있을 것이라고 기대하는 욱제의 표정
욱제의 질문에 답하고 함께 엠티를 떠나자!!
첫 번째 줄에 수열 A의 길이 N과 질문의 개수 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 300,000)
두 번째 줄에 N개의 정수 A1, A2, ..., AN 이 공백으로 구분되어 주어진다. Ai 는 수열 A의 i 번째 수이다. (1 ≤ Ai ≤ 1,000)
세 번째 줄부터 Q개의 줄에 걸쳐 욱제의 질문을 의미하는 두 수 L, R이 공백으로 구분되어 주어진다. (1 ≤ L ≤ R ≤ N)
주어지는 모든 입력은 자연수이다.
Q개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.
5 6 2 5 1 4 3 1 5 2 4 3 3 1 3 2 5 4 5
15 9 3 6 14 9
[2, 5, 1, 4, 3]을 비내림차순으로 정렬하면 [1, 2, 3, 4, 5]이다.
5 3 2 5 1 2 3 1 3 2 3 1 5
5 4 13
[2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다.
비내림차순은 원소가 감소하지 않는 (같거나 증가하는) 순서를 말한다.
while (Q--) {
int sum = 0, L, R;
scanf(“%d %d”, &L, &R);
for (int i = L; i <= R; i++) {
sum += a[i];
}
printf(“%d\n”, sum);
}위와 같이 각 질문마다 반복문을 매번 돌려서 답을 계산하면, 시간복잡도가 O(QN)이 되므로 시간 초과를 받게 된다. 다른 방법을 이용해 문제를 해결해야 한다.